È possibile valutare la sicurezza per codice arbitrario a livello di codice?

8

Ultimamente ho pensato molto al codice sicuro. Thread-safe. Memory-safe. Non-andando-a-esplodere-nella-tua-faccia-con-un-segfault sicuro. Ma per motivi di chiarezza nella domanda, utilizziamo il modello di sicurezza di Rust come nostra definizione.

Spesso, garantire la sicurezza è un problema un po 'troppo grande, perché, come dimostrato dal bisogno di Rust di unsafe , ci sono alcune idee di programmazione molto ragionevoli, come la concorrenza, che impossibile essere implementato in Rust senza utilizzare la parola chiave unsafe . Anche se la concorrenza può essere resa perfettamente sicura con i blocchi, i mutex, i canali e l'isolamento della memoria o quello che hai, è necessario lavorare fuori del modello di sicurezza di Rust con unsafe , e quindi assicurare manualmente al compilatore che, "Sì, so cosa sto facendo. Sembra poco sicuro, ma ho dimostrato matematicamente che è perfettamente sicuro."

In genere, tuttavia, si tratta di creare manualmente modelli di queste cose e dimostrare di essere al sicuro con teorici . Sia dal punto di vista dell'informatica (è possibile) sia da un punto di vista pratico (prenderà la vita dell'universo), è ragionevole immaginare un programma che prende un codice arbitrario in un linguaggio arbitrario e valuta se è o meno " Ruggine sicura "?

Avvertimenti :

  • Una semplice spiegazione su questo è sottolineare che il programma potrebbe essere inatteso e quindi il problema di interruzione fallisce noi. Diciamo che qualsiasi programma alimentato al lettore è garantito per arrestare
  • Mentre l'obiettivo è "codice arbitrario in una lingua arbitraria", sono ovviamente consapevole che ciò dipende dalla familiarità del programma con la lingua scelta, che considereremo un dato
posta TheEnvironmentalist 08.11.2018 - 06:14
fonte

3 risposte

7

Ciò di cui stiamo parlando in definitiva qui è compilazione tempo vs runtime.

Compilare errori nel tempo, se ci pensate, in ultima analisi equivale al fatto che il compilatore sia in grado di determinare quali problemi avete nel vostro programma prima ancora che venga eseguito. Ovviamente non è un compilatore di "linguaggio arbitrario", ma tornerò tra poco. Il compilatore, in tutta la sua infinita saggezza, non elenca comunque il problema ogni che può essere determinato dal compilatore. Questo dipende in parte dal modo in cui il compilatore è scritto, ma la ragione principale è che molte cose sono determinate in runtime .

Errori di runtime, come ben sai sono sicuro che sono, qualsiasi tipo di errore che si verifica durante l'esecuzione del programma stesso. Ciò include la divisione per zero, eccezioni del puntatore nullo, problemi hardware e molti altri fattori.

La natura degli errori di runtime significa che non è possibile anticipare detti errori in fase di compilazione. Se potessi, verrebbero quasi certamente controllati al momento della compilazione. Se si è in grado di garantire che un numero sia zero al momento della compilazione, è possibile eseguire alcune conclusioni logiche, ad esempio la divisione di qualsiasi numero per quel numero comporterà un errore aritmetico causato dalla divisione per zero.

Come tale, in un modo molto reale, il nemico che garantisce programmaticamente il corretto funzionamento di un programma sta eseguendo verifiche di runtime piuttosto che verifiche della compilazione del tempo. Un esempio di questo potrebbe essere eseguire un cast dinamico per un altro tipo. Se questo è permesso, tu, il programmatore, stai essenzialmente scavalcando la capacità del compilatore di sapere se è una cosa sicura da fare. Alcuni linguaggi di programmazione hanno deciso che questo è accettabile mentre altri ti avvertiranno almeno in fase di compilazione.

Un altro buon esempio potrebbe essere che i null siano parte della lingua, poiché le eccezioni del puntatore nullo potrebbero verificarsi se si accettano valori nulli. Alcune lingue hanno eliminato completamente questo problema impedendo che le variabili non dichiarate esplicitamente fossero in grado di mantenere i valori nulli da dichiarare senza che venisse assegnato immediatamente un valore (ad esempio, prendere Kotlin). Sebbene non sia possibile eliminare un errore di runtime delle eccezioni del puntatore nullo, è possibile impedire che ciò accada rimuovendo la natura dinamica della lingua. In Kotlin, puoi forzare la possibilità di mantenere valori nulli, naturalmente, ma è ovvio che si tratta di un metaforico "gli acquirenti si guardano bene", come devi esplicitamente dichiararlo come tale.

Potresti concettualmente avere un compilatore in grado di controllare gli errori in ogni lingua? Sì, ma probabilmente sarebbe un compilatore goffo e altamente instabile in cui dovresti necessariamente fornire in anticipo il linguaggio da compilare. Inoltre, non è in grado di conoscere molte cose sul tuo programma, più di quanto i compilatori di specifiche lingue conoscano certe cose a riguardo, come ad esempio il problema dell'arresto, come hai menzionato. A quanto pare, una buona quantità di informazioni che potrebbero essere interessanti da apprendere su un programma sono impossibili da raccogliere. Questo è stato dimostrato, quindi non è probabile che cambi in qualsiasi momento presto.

Ritorno al punto principale. I metodi non sono automaticamente thread-safe. C'è una ragione pratica per questo, che è che i metodi thread-safe sono anche più lenti anche quando i thread non vengono utilizzati. Rust decide che possono eliminare i problemi di runtime rendendo i metodi thread safe per impostazione predefinita, e questa è la loro scelta. Tuttavia, ha un costo.

Potrebbe essere possibile provare matematicamente la correttezza di un programma, ma sarebbe con l'avvertenza che avresti letteralmente zero funzioni di runtime nella lingua. Saresti in grado di leggere questa lingua e sapere cosa fa senza sorprese. La lingua probabilmente avrebbe un aspetto molto matematico, e probabilmente non è una coincidenza lì. La seconda avvertenza è che si verificano errori di runtime ancora , che potrebbero non avere nulla a che fare con il programma stesso. Pertanto, il programma può essere dimostrato corretto, supponendo che una serie di ipotesi sul computer su cui viene eseguito siano accurate e non cambino, il che, naturalmente, fa accade comunque e spesso.

    
risposta data 08.11.2018 - 09:01
fonte
2

I sistemi di tipo sono prove automaticamente verificabili di alcuni aspetti della correttezza. Ad esempio, il sistema di tipi di Rust può dimostrare che un riferimento non sopravvive all'oggetto di riferimento o che un oggetto di riferimento non viene modificato da un altro thread.

Ma i sistemi di tipo sono piuttosto limitati:

  • Si imbattono rapidamente in problemi di decidibilità. In particolare, il sistema di tipo stesso dovrebbe essere decidibile, eppure molti sistemi di tipo pratico sono accidentalmente Turing Complete (incluso C ++ a causa di modelli e Rust a causa di tratti). Inoltre, alcune proprietà del programma che stanno verificando potrebbero essere indecidibili nel caso generale, in particolare se alcuni programmi si fermano (o divergono).

  • Inoltre, i sistemi di tipo dovrebbero essere eseguiti rapidamente, idealmente nel tempo lineare. Non tutte le dimostrazioni possibili dovrebbero essere presenti nel sistema di tipi. Per esempio. l'intera analisi del programma viene solitamente evitata e le dimostrazioni sono mirate a singoli moduli o funzioni.

A causa di queste limitazioni, i sistemi di tipo tendono a verificare solo le proprietà abbastanza deboli che sono facili da dimostrare, ad es. che una funzione viene chiamata con valori di tipo corretto. Tuttavia, anche questo limita notevolmente l'espressività, quindi è normale avere soluzioni alternative (come interface{} in Vai, dynamic in C #, Object in Java, void* in C) o anche usare linguaggi che cancellano completamente la tipizzazione statica .

Le proprietà più forti che verifichiamo, meno espressive si otterranno in genere. Se hai scritto Rust, conoscerai questi momenti di "combattimento con il compilatore" in cui il compilatore rifiuta il codice apparentemente corretto, perché non è stato in grado di dimostrare la correttezza. In alcuni casi, è non possibile esprimere un certo programma in Rust anche quando crediamo di poter dimostrare la sua correttezza. Il meccanismo unsafe in Rust o C # ti consente di sfuggire ai confini del sistema di tipi. In alcuni casi, il rinvio dei controlli al runtime può essere un'altra opzione, ma ciò significa che non possiamo rifiutare alcuni programmi non validi. Questa è una questione di definizione. Un programma Rust che il panico è sicuro per quanto riguarda il sistema di tipi, ma non necessariamente dalla prospettiva di un programmatore o utente.

Le lingue sono progettate insieme al loro sistema di tipi. È raro che un nuovo sistema di tipi venga imposto su una lingua esistente (ma si veda ad esempio MyPy, Flow o TypeScript). Il linguaggio proverà a semplificare la scrittura di codice conforme al sistema di tipi, ad es. offrendo annotazioni di tipo o introducendo strutture di controllo del flusso facili da dimostrare. Lingue diverse possono finire con soluzioni diverse. Per esempio. Java ha il concetto di final di variabili che vengono assegnate esattamente una volta, in modo simile alle variabili% di% non co_de di Rust:

final int x;
if (...) { ... }
else     { ... }
doSomethingWith(x);

Java ha le regole di sistema dei tipi per determinare se tutti i percorsi assegnano la variabile o terminano la funzione prima che la variabile possa essere consultata. Al contrario, Rust semplifica questa dimostrazione non avendo le variabili dichiarate ma non disegnate, ma consente di restituire i valori dalle istruzioni del flusso di controllo:

let x = if ... { ... } else { ... };
do_something_with(x)

Questo sembra un punto davvero secondario quando si cerca di capire l'assegnazione, ma la verifica dell'ottimizzazione è estremamente importante per le dimostrazioni relative al ciclo di vita.

Se dovessimo applicare un sistema di tipo Rust in Java, avremmo problemi molto più grandi di questo: gli oggetti Java non sono annotati con durata, quindi dovremmo trattarli come mut o &'static SomeClass . Ciò indebolirebbe qualsiasi prova risultante. Java non ha nemmeno un concetto di immutabilità di livello di tipo, quindi non possiamo distinguere tra Arc<dyn SomeClass> e & types. Dovremmo trattare qualsiasi oggetto come una cella o un mutex, anche se questo potrebbe assumere garanzie più forti di quelle offerte da Java (cambiare un campo Java non è protetto da thread se non sincronizzato e volatile). Infine, Rust non ha alcun concetto di ereditarietà dell'implementazione in stile Java.

TL; DR: i sistemi di tipi sono teorizzatori. Ma sono limitati da problemi di decidibilità e problemi di prestazioni. Non puoi semplicemente prendere un sistema di tipi e applicarlo a una lingua diversa, poiché la sintassi della lingua del target potrebbe non fornire le informazioni necessarie e perché la semantica potrebbe essere incompatibile.

    
risposta data 08.11.2018 - 11:46
fonte
2

Quanto è sicuro la sicurezza?

Sì, è quasi possibile scrivere un verificatore di questo tipo: il tuo programma deve solo restituire UNSAFE costante. Avrai ragione il 99% delle volte

Perché anche se si esegue un programma Rust sicuro, qualcuno può ancora staccare la spina durante la sua esecuzione: così il tuo programma potrebbe fermarsi anche se teoricamente non dovrebbe farlo.

E anche se il tuo server è in esecuzione in una gabbia faraday in un bunker, un processo vicino potrebbe eseguire un exploit di martello pneumatico e fare un capovolgimento in uno dei tuoi presunti programmi Rust.

Quello che sto cercando di dire è che il tuo software funzionerà in un ambiente non deterministico e molti fattori esterni potrebbero influenzare l'esecuzione.

Scherzo a parte, verifica automatica

Esistono già analizzatori di codici statici in grado di individuare costrutti di programmazione rischiosi (variabili non inizializzate, buffer overflow, ecc.). Questi funzionano creando un grafico del programma e analizzando la propagazione dei vincoli (tipi, intervalli di valori, sequenziamento).

Questo tipo di analisi viene comunque eseguito da alcuni compilatori per motivi di ottimizzazione.

È certamente possibile fare un ulteriore passo avanti, analizzare anche la concorrenza e fare deduzioni sulla propagazione dei vincoli su più thread, sincronizzazione e condizioni di gara. Tuttavia, molto rapidamente ti imbatterai nel problema dell'esplosione combinatoria tra i percorsi di esecuzione e molte incognite (I / O, schedulazione del sistema operativo, input dell'utente, comportamento di programmi esterni, interruzioni, ecc.) Che trasmetteranno i vincoli noti alla loro nuda minimo e rendere molto difficile trarre utili conclusioni automatizzate sul codice arbitrario.

    
risposta data 08.11.2018 - 13:32
fonte

Leggi altre domande sui tag