5 ms·

> determining whether a given file constitutes a virus seems equivalent to solving the halting problem. In fact (for a sufficiently rigorous definition of viru

by Wilfred 16y ago

> determining whether a given file constitutes a virus seems equivalent to solving the halting problem. In fact (for a sufficiently rigorous definition of virus), it is provably the case that we cannot determine whether a file is a virus, using an argument very similar to a halting problem proof. You might be interested in 'Computer viruses: theory and experiments' by Fred Cohen for the full working-out of the proof.

bediger 16y ago
Thanks for the tip on the Fred Cohen paper. I have seen arguments to the effect that since a virus doens't run with an infinite memory, you can indeed determine whether a disk file represents a virus or not. As Alfred North Whitehead once said: "Necessity is the mother of invention" is a silly proverb. "Necessity is the mother of futile dodges" is much nearer the truth."
derefr 16y ago
Viruses are really a matter of computer action given user intent—and therefore are able to be solved not just by detection of incongruous computer action, but also by detection of incongruous user intent. For example, imagine that instead of WIMP, all interactions with a computer occurred through a hierarchical, task-based UI (similar to, e.g., emacs org-mode) where you had to specify a high-level goal you wanted to accomplish before you could set about running programs to do it. If the computer knows that what you want to get done doesn't involve deleting files, then any program you run that does delete files has either been executed in error, or is acting not according to the user's command.
- dexen 16y ago
  > If the computer knows that what you want to get done doesn't involve deleting files, then any program you run that does delete files has either been executed in error, or is acting not according to the user's command. Tell that the authors of certain popular PDF reader software, currently version X. Which, on the surface at least, has only one goal: display content of a PDF file. But scratch the surface and you note it may involve creation of temporary file of sorts. And perhaps loading additional libraries every now and then. And perhaps executing code contained in the document (if it's a form with validation code, for example). There are countless ways of achieving a goal, and which is better depends on situation. Pinning everything down to some one-true-way won't do. And expressing the possibilities is, well, designing & programming. With the usual assortment of bugs, up to and including vulnerabilities. So no, you can't have a secure system / virus detection based on user stating general high-level goal.
  - derefr 16y ago
    > But scratch the surface and you note it may involve creation of temporary file of sorts. Alright, s/file/document/g in my statement above—a "document" being some chunk of information the user values, and which the program doesn't have any "ownership" of unless the user explicitly delegates said ownership to it. Think of SELinux: a program would have to request a right to delete the user's files, although it would be perfectly allowed to delete its own files. Except, in this case, instead of the program presenting a security elevation dialog to get permission to delete a document (or do any of an infinite number of other fine-grained things), you'd specify its permissions ahead of time, in the form of a natural-language phrase that is fuzzily-keyed in a HTM memory-base to sub-goals and sibling-goals, each of which eventually reach leaf nodes representing granted permissions. Also note that, if I specify my goal as viewing a PDF document, I am explicitly telling the computer I that running a script is not something I want to be doing. If I wanted that, I would say I want to interact with a PDF document (or, in more natural-language terms, "fill out a form", of which "interact with a PDF file" would be one of the child nodes.)
    - dexen 16y ago
      > Also note that, if I specify my goal as viewing a PDF document, I am explicitly telling the computer I that running a script is not something I want to be doing. LOL, no, you don't. At least in general, for interacting with rich documents. Imagine for a moment disabling JavaScript in your browser and browsing HN. Or any other important website. Now go ahead and actually try that -- you'll find that you've vastly underestimated the impact on usability. That you've missed a lot of functionality that is seamless, unobtrusive -- and you only notice its importance once its gone. Thank you, I rest my case [0] [1]. > (...) you'd specify its permissions ahead of time, in the form of a natural-language phrase that is fuzzily-keyed in a HTM memory-base (...) It strikes me as something very open to attacking special cases. Like weak encryption -- works most of the time, but breakable by somebody with incentives. But that's just a hitch, no hard facts. The UX reeks of the UAC -- I can't see any bottom-line minding company repeating that mistake. ---- [0] yes, I know some people use the `noscript' plugin or similar. Still, the second basic functionality of such plugin is whitelisting websites for enabling JS on 'em. [1] In any case, a bug in interpreter of any no-scripted (`plain data') document can give way to memory corruption and code injection. Happened way too many times with browsers, movie players etc. Exploit hidden in PNG? Heck, why not?
xyzzyz 16y ago
You can state it even more generally -- given any task, there is no algorithm to check whether a given program does it. http://en.wikipedia.org/wiki/Rice_theorem http://en.wikipedia.org/wiki/Rice_theorem
- bediger 16y ago
  Good reference, thank you. But... Tell that to any software development manager, and you'll get a long lasting blank look. Too many people and corporations have lied to the managerial class for too long. I've had managers tell me that I can estimate development time exactly, while giving me a short, finite time span in which to generate the estimate.

by Wilfred 16y ago

bediger 16y ago

Thanks for the tip on the Fred Cohen paper. I have seen arguments to the effect that since a virus doens't run with an infinite memory, you can indeed determine whether a disk file represents a virus or not. As Alfred North Whitehead once said: "Necessity is the mother of invention" is a silly proverb. "Necessity is the mother of futile dodges" is much nearer the truth."

derefr 16y ago

Viruses are really a matter of computer action given user intent—and therefore are able to be solved not just by detection of incongruous computer action, but also by detection of incongruous user intent. For example, imagine that instead of WIMP, all interactions with a computer occurred through a hierarchical, task-based UI (similar to, e.g., emacs org-mode) where you had to specify a high-level goal you wanted to accomplish before you could set about running programs to do it. If the computer knows that what you want to get done doesn't involve deleting files, then any program you run that does delete files has either been executed in error, or is acting not according to the user's command.

dexen 16y ago
> If the computer knows that what you want to get done doesn't involve deleting files, then any program you run that does delete files has either been executed in error, or is acting not according to the user's command. Tell that the authors of certain popular PDF reader software, currently version X. Which, on the surface at least, has only one goal: display content of a PDF file. But scratch the surface and you note it may involve creation of temporary file of sorts. And perhaps loading additional libraries every now and then. And perhaps executing code contained in the document (if it's a form with validation code, for example). There are countless ways of achieving a goal, and which is better depends on situation. Pinning everything down to some one-true-way won't do. And expressing the possibilities is, well, designing & programming. With the usual assortment of bugs, up to and including vulnerabilities. So no, you can't have a secure system / virus detection based on user stating general high-level goal.
- derefr 16y ago
  > But scratch the surface and you note it may involve creation of temporary file of sorts. Alright, s/file/document/g in my statement above—a "document" being some chunk of information the user values, and which the program doesn't have any "ownership" of unless the user explicitly delegates said ownership to it. Think of SELinux: a program would have to request a right to delete the user's files, although it would be perfectly allowed to delete its own files. Except, in this case, instead of the program presenting a security elevation dialog to get permission to delete a document (or do any of an infinite number of other fine-grained things), you'd specify its permissions ahead of time, in the form of a natural-language phrase that is fuzzily-keyed in a HTM memory-base to sub-goals and sibling-goals, each of which eventually reach leaf nodes representing granted permissions. Also note that, if I specify my goal as viewing a PDF document, I am explicitly telling the computer I that running a script is not something I want to be doing. If I wanted that, I would say I want to interact with a PDF document (or, in more natural-language terms, "fill out a form", of which "interact with a PDF file" would be one of the child nodes.)
  - dexen 16y ago
    > Also note that, if I specify my goal as viewing a PDF document, I am explicitly telling the computer I that running a script is not something I want to be doing. LOL, no, you don't. At least in general, for interacting with rich documents. Imagine for a moment disabling JavaScript in your browser and browsing HN. Or any other important website. Now go ahead and actually try that -- you'll find that you've vastly underestimated the impact on usability. That you've missed a lot of functionality that is seamless, unobtrusive -- and you only notice its importance once its gone. Thank you, I rest my case [0] [1]. > (...) you'd specify its permissions ahead of time, in the form of a natural-language phrase that is fuzzily-keyed in a HTM memory-base (...) It strikes me as something very open to attacking special cases. Like weak encryption -- works most of the time, but breakable by somebody with incentives. But that's just a hitch, no hard facts. The UX reeks of the UAC -- I can't see any bottom-line minding company repeating that mistake. ---- [0] yes, I know some people use the `noscript' plugin or similar. Still, the second basic functionality of such plugin is whitelisting websites for enabling JS on 'em. [1] In any case, a bug in interpreter of any no-scripted (`plain data') document can give way to memory corruption and code injection. Happened way too many times with browsers, movie players etc. Exploit hidden in PNG? Heck, why not?

xyzzyz 16y ago

You can state it even more generally -- given any task, there is no algorithm to check whether a given program does it. http://en.wikipedia.org/wiki/Rice_theorem http://en.wikipedia.org/wiki/Rice_theorem

bediger 16y ago
Good reference, thank you. But... Tell that to any software development manager, and you'll get a long lasting blank look. Too many people and corporations have lied to the managerial class for too long. I've had managers tell me that I can estimate development time exactly, while giving me a short, finite time span in which to generate the estimate.