Live data from Hacker News

Hacking with LaTeX

0day.work

31–40 of 41 posts

Re: Hacking with LaTeX

#31
post #18
post #9

Earlier quoted context omitted.

The halting problem makes it impossible to consistently answer the question "Will this instruction be executed ?" This is why you can't know if the code is malicious : you can't (always) infer meaningful properties about the code (Will it write something on the disk ?...).

> The halting problem makes it impossible to consistently answer the question "Will this instruction be executed ?" In fact, Rice's theorem says that it's impossible more generally to answer any question about arbitrary code—so no work-arounds like "OK, I can't tell if a particular instruction is executed, but I can just test whether this program is 'safe'" (say, performs no I/O).

Technically, Rice's theorem only applies to "non-trivial" questions, i.e. those which are true for some programs and false for others, which are properties of the function being computed.

Hence we can work around the theorem, by either turning the questions we care about into trivial questions, or by turning questions of the function into questions about the implementation.

For example, we might ask the question "Will program P fire the missiles?". If the answer is yes for some P and false for others, then we cannot answer it for arbitrary P.

We can work around it by weakening the question to become trivial, e.g. "Is program P capable of firing missiles?". If the language allows missiles to be fired, then the answer is trivially yes for all P; if not then the answer is trivially no.

Alternatively, we can change the question to one of implementation, e.g. "Does program P contain the instruction?". Assuming that our programming language contains such an instruction, this is a non-trivial question. However, since it's a question about the implementation (does that instruction appear) rather than the function being computed (which may or may not fire missiles), Rice's theorem doesn't forbid us from answering it.

Re: Hacking with LaTeX

#32
post #18

Earlier quoted context omitted.

> The halting problem makes it impossible to consistently answer the question "Will this instruction be executed ?" In fact, Rice's theorem says that it's impossible more generally to answer any question about arbitrary code—so no work-arounds like "OK, I can't tell if a particular instruction is executed, but I can just test whether this program is 'safe'" (say, performs no I/O).

Technically, Rice's theorem only applies to "non-trivial" questions, i.e. those which are true for some programs and false for others, which are properties of the function being computed. Hence we can work around the theorem, by either turning the questions we care about into trivial questions, or by turning questions of the function into questions about the implementation. For example, we might ask the question "Wil…

> However, since it's a question about the implementation (does that instruction appear) rather than the function being computed (which may or may not fire missiles)

On common architectures where code is data is code, this sounds hard to detect as the program could build a buffer of commands that end up firing the missile, without any obvious "fire the missile" sequence present in the binary? For example, the program could inflict a stack overflow on itself.

Re: Hacking with LaTeX

#33
post #32

Earlier quoted context omitted.

Technically, Rice's theorem only applies to "non-trivial" questions, i.e. those which are true for some programs and false for others, which are properties of the function being computed. Hence we can work around the theorem, by either turning the questions we care about into trivial questions, or by turning questions of the function into questions about the implementation. For example, we might ask the question "Wil…

> However, since it's a question about the implementation (does that instruction appear) rather than the function being computed (which may or may not fire missiles) On common architectures where code is data is code, this sounds hard to detect as the program could build a buffer of commands that end up firing the missile, without any obvious "fire the missile" sequence present in the binary? For example, the program…

> the program could build a buffer of commands that end up firing the missile, without any obvious "fire the missile" sequence present in the binary

Absolutely, the work-arounds are just that; they don't answer the original question.

In the case of "Is program P capable of firing missiles?", this will be 'yes' for many programs which don't fire missiles, so it's an over-approximation of missile-firing.

In the case of "Does program P contain the instruction?", this could, as you say, under-approximate missile firing.

If the language allows running data as code, then we can handle this in a conservative way, i.e. 'Could program P execute a instruction?', which would be true if P contains '', true if P contains 'eval' (since the evaluated code could fire the missiles), etc. and false otherwise. We can make our questions (AKA our type systems) arbitrarily clever, but they will only ever approximate the answers to questions forbidden by Rice's theorem. Usually it's best to make conservative approximations, i.e. turning "does XYZ happen?" into "could XYZ happen?", assuming that it could, and only answering 'no' if we can prove otherwise.

As far as cases like 'the program could inflict a stack overflow on itself', these would all be handled in our model of the language (equivalent to the list of conditions I wrote above which affected whether we answer true or false). Again, this should be conservative, so it's likely that for edge-cases like 'inflicting a stack overflow on itself', there might not be much we can say about the program's behaviour; in which case we'd get a lot of 'yes' answers to our 'could XYZ happen?' questions, simply because we can't rule those things out.

Re: Hacking with LaTeX

#34

It's LaTeX, not Latex. And it's TeX-the-language (as opposed to TeX-the-program) that's Turing-complete; LaTeX is a macro package written in TeX. Also, from 2011: https://cseweb.ucsd.edu/~hovav/dist/tex-login.pdf TeX files are a common method of collaboration for computer science professionals. It is widely assumed by users that LaTeX files are safe; that is, that no significant harm can come of running LaTeX on an a…

[deleted]

Re: Hacking with LaTeX

#35

Earlier quoted context omitted.

Well, take things that way: if your language is not Turing-complete, you could lock things down so that no crazy stuff happens, and prove that there is no way to bypass the security --assuming this problem is decidable, which can be the case if the language is not Turin-complete, but is hopeless otherwise. So it's a bit like saying "well, both are dogs so both can bite", when one is well-trained and leashed, and the…

Can you give an example of how the halting problem allows one to make it impossible/difficult to detect malicious code? I sort of get what you are saying, that Turing completeness makes analysis more difficult, but I still don't see what it has to do with security.

A turing complete program could, by definition, generate any other turing complete program.

In theory, you can statically analyse any program to prove that it doesn't contain malicious code (for some definition of malicious). But if a program is turing complete, you cannot predict all of its possible outputs and therefore, cannot rule out the possibility of a malicious output.

The halting problem is what prevents you doing the analysis, not what introduces the possibility of maliciousness.

Re: Hacking with LaTeX

#36

It's LaTeX, not Latex. And it's TeX-the-language (as opposed to TeX-the-program) that's Turing-complete; LaTeX is a macro package written in TeX. Also, from 2011: https://cseweb.ucsd.edu/~hovav/dist/tex-login.pdf TeX files are a common method of collaboration for computer science professionals. It is widely assumed by users that LaTeX files are safe; that is, that no significant harm can come of running LaTeX on an a…

>It's LaTeX, not Latex.

Who cares, really?

Re: Hacking with LaTeX

#37
post #18

Earlier quoted context omitted.

> The halting problem makes it impossible to consistently answer the question "Will this instruction be executed ?" In fact, Rice's theorem says that it's impossible more generally to answer any question about arbitrary code—so no work-arounds like "OK, I can't tell if a particular instruction is executed, but I can just test whether this program is 'safe'" (say, performs no I/O).

Technically, Rice's theorem only applies to "non-trivial" questions, i.e. those which are true for some programs and false for others, which are properties of the function being computed. Hence we can work around the theorem, by either turning the questions we care about into trivial questions, or by turning questions of the function into questions about the implementation. For example, we might ask the question "Wil…

> Hence we can work around the theorem, by either turning the questions we care about into trivial questions, or by turning questions of the function into questions about the implementation.

You're quite right that my omission of 'non-trivial' makes the theorem as stated wrong; sorry!

I like your statement of the second work-around (elaborated below (https://news.ycombinator.com/item?id=11260034)), as (essentially) what type systems do, especially with the emphasis on why it must be over-conservative.

Although your statement of the first work-around is technically correct, I think that it is important to emphasise (as you clearly know, but others may not) how useless it is (on the program level): questions of this sort are necessarily about the language, not about the program.

Re: Hacking with LaTeX

#38

It's LaTeX, not Latex. And it's TeX-the-language (as opposed to TeX-the-program) that's Turing-complete; LaTeX is a macro package written in TeX. Also, from 2011: https://cseweb.ucsd.edu/~hovav/dist/tex-login.pdf TeX files are a common method of collaboration for computer science professionals. It is widely assumed by users that LaTeX files are safe; that is, that no significant harm can come of running LaTeX on an a…

>It's LaTeX, not Latex. Who cares, really?

People who cultivate a level of attention to detail that is seen as pedantic by many, but that is utterly essential for creating high quality software.

Re: Hacking with LaTeX

#40

Earlier quoted context omitted.

>It's LaTeX, not Latex. Who cares, really?

People who cultivate a level of attention to detail that is seen as pedantic by many, but that is utterly essential for creating high quality software.

Grammar essential for high quality software? Many would disagree.

I'd say its only essential for being no fun at parties.

Post reply on HN