Quale applicabilità deve risolvere il problema di stallo?

Esperto affermato ... che sarei io (anche se non con questo nome - uso uno pseudonimo perché sono tremendamente umile). Permettimi di rispondere, quindi.

Il "problema dell'arresto" è in realtà un esempio dell'impossibilità di decidere (per un computer) se un determinato programma si fermerà o meno. Certo, molti programmi sono decidibili, ma non tutti. Le persone tendono a pensare che se potessimo "prevedere con precisione il comportamento" dei programmi per computer, il malware non sarebbe possibile. Questo è eccessivamente semplicistico, per i seguenti motivi:

• Il "problema dell'arresto" consiste nel decidere se un programma per computer si fermerà, per un dato input che è noto a priori . Questo modello funziona solo su programmi che sono puramente di calcolo e non eseguono operazioni di I / O. Per definizione, questo non si applica a nessuna applicazione connessa a Internet o controllata da un essere umano. A titolo illustrativo, prendi in considerazione un'applicazione che esegue un video. Questo non si fermerà mai finché l'utente umano fa clic sul pulsante di riavvolgimento. Ma potrebbe fermarsi (e dovrebbe essere facile da dimostrare) se l'utente fa non fare clic su qualsiasi pulsante.

• Decidability riguarda la possibilità di valutare una data funzione , ma non se può essere valutato efficientemente . Se si desidera che un antivirus esegua la scansione del malware, si desidera ottenere la risposta entro 2 o 3 secondi, non tra dieci anni. Questa nozione di decidibilità non cattura tutte le cose a cui siamo interessati.

• Noi possiamo avere dei requisiti. Prendi in considerazione un'applicazione Java. È scritto in bytecode che è suscettibile di dimostrazioni automatiche (efficienti). Vale a dire, la JVM dimostrerà , in un modo molto formale, che il codice è conforme alle regole di tipo di Java (che non chiama mai un metodo su una classe che non presenta quel metodo). Non è possibile fare genericamente una tale prova, su ogni possibile sequenza di istruzioni bytecode; ma codice Java valido è bytecode che può essere provato in questo modo. Ciò significa che nella pratica è possibile far rispettare i requisiti di "proofability" per il codice esistente. In un punto di vista "problema di interruzione", sarebbe come affermare che i programmi per i quali il comportamento di arresto non può essere determinato in modo assoluto (e rapidamente) sarà impedito senza cerimonie dall'esecuzione.

• Non ci interessa sapere se un programma fermerà , ma se un programma farà cose malvagie . Sono tutto per un computer per modificare il mio conto in banca ... finché questo è quello che voglio. La differenza tra me, l'utente umano / ursino, la gestione dei miei soldi attraverso il sito Web della banca e un malware, che travasa il mio prezioso oro attraverso il sito Web della banca, non è qualcosa che esiste nel mondo dei computer. Non c'è idea di Male nei computer. Se voglio la sicurezza, devo prima definire con tutta la precisione necessaria cosa esattamente voglio consentire ai computer, e cosa non voglio. Prima di chiedermi se un programma per computer sarà in grado di decidere automaticamente se le mie proprietà di sicurezza di base saranno rispettate da una determinata parte di codice, devo prima definire queste proprietà, e quella parte iniziale del lavoro è Lungi dall'essere fatto. Indurre il computer a indovinare cosa è buono è un vecchio problema che sembra difficile.

Per questi motivi, sostengo che invocare il "problema dell'arresto" sia una scusa scadente. Evidenzia il fatto che abbiamo a che fare con problemi che richiedono un po 'più di pensiero rispetto alla scrittura di un altro sito Web PHP. Ma not implica che la sicurezza non è possibile, solo che la Scienza non troverà uno strumento magico che la risolverà senza sforzo (perché questo Blessed +3 Hammer of Decidability risolverà anche il problema dell'arresto, che non è matematicamente possibile)

Can an attacker use the halting problem as a form of an attack?

Non è quello che usa un attacco attackit comportamentistico complesso ? Il tuo server utilizza un algoritmo che ha un comportamento peggiore nel peggiore dei casi, forse come che non termina su sequenze di input speciali. Poiché non esiste un metodo generale, hai difficoltà a distinguere quale speciale sequenza di input potrebbe causare un loop infinito nel tuo algoritmo elegante.