Computervirussen en Cohen's onmogelijkheidsresultaat

An English version is also available.

Het achtste gezichtsbepalende probleem voor het informaticaonderzoek uit de lijst van tien gezichtsbepalende problemen opgesteld door Prof.dr. Jan Bergstra, zie [NOAG-ict] (pdf, blz. 52) luidt:

"Probleem 8: Geef een overtuigende theorie van computervirussen en soortgelijke krachtige vormen van artificial life. De sterke start door Cohen [C84] in 1984 heeft anno 2005 opmerkelijk weinig follow-up gehad."

Ik zal op deze webpagina proberen een aantal van de aspecten van dit probleem uiteen te zetten en enige literatuur en links naar relevante websites te geven.

Aspecten:

• Wat is het onmogelijkheidsresultaat van Cohen?
• Waar is het goed voor?
• Hoe gaat het bewijs van Cohen?
• Zijn er mensen in Nederland of elders die hieraan werken?
• Wie ben ik?

Wat is het onmogelijkheidsresultaat van Cohen?

Simpel geformuleerd: gegeven een redelijke klasse van computer programma's (bv. de while-programs) is het is niet mogelijk te bepalen of een computer programma bij uitvoering een virus zal verspreiden.

Literatuur

• F. Cohen. Computer viruses - theory and experiments, 1984. Computers & Security 6(1): 22-35, 1987.

Waar is het goed voor?

Hoe gaat het bewijs van Cohen?

Terug naar de aspecten.

Zijn er mensen in Nederland of elders die hieraan werken?

Literatuur

• J.A. Bergstra and A. Ponse. A bypass of Cohen's impossibility result. In P.M.A. Sloot, A.G. Hoekstra, T. Priol, A. Reinefeld, M. Bubak (editors). Advances in Grid Computing - EGC 2005, LNCS 3470, pages 1097-1106. Springer-Verlag, 2005. Also appeared as Electronic report PRG0501, Programming Research Group, University of Amsterdam, 2005.
• J.A. Bergstra, I. Bethke, and A. Ponse. Thread algebra and risk assessment services. In Costas Dimitracopoulos, Ludomir Newelski, Dag Normann and John R. Steel (eds.), Proceedings Logic Colloquium 2005, pages 1-17, 2007.
• A. Ponse and M.B. van der Zwaag. Risk assessment for one-counter threads. Theory of Computing Systems, 43:563-582, 2008.

Wie ben ik dat ik hierover een webpagina maak?

Alban Ponse; zie desgewenst mijn home page. Ik ben in 1992 gepromoveerd op een proefschrift in de procesalgebra (Process Algebras with Data).

Terug naar het begin.