3 ms·

I believe the year numbers were used by logicallee only as an example. Of course, if somebody is trying this, they need to figure out a different (smaller) tim

by vog 10y ago

I believe the year numbers were used by logicallee only as an example. Of course, if somebody is trying this, they need to figure out a different (smaller) time scale that actually works. In the worst case, you have to follow each commit in the version control system of the compiler, but I'm pretty sure you don't need to do it that fine grained.

logicallee 10y ago
yes. I'm pretty shocked Manishearth didn't get that I was just giving examples of the process with placeholder dates, since I started my comment explicitly stating (I add emphasis here): >you use an old compiler binary that didn't have the attack yet to compile the latest source code that it is able to compile, then use that to compile the latest it can compile, and so forth. in trying to find the "latest source code that it is able to compile" you can do a binary search backward from the current version of the source code. it doesn't take long to find the latest version for each one (i.e. the latest each one compiles without error, into a working binary that passes some test suite). And anyway whenever you're binary-searching forward (i.e. after any point where the binary search yields ""greater-than" because the one you just tried compiled) then you can just use the version you just successfully compiled. Let me illustrate what i mean with this binary search: so if we're at version 1 million today, which the version 7 doesn't compile, then you try version 7 on version 500,000 (it'll fail), then on version 250,000 (it'll fail), version 125,000 (it'll fail), version 125,000 (it'll fail), version 62,500 (it'll fail), version 31,250 (it'll fail), version 62500 (fail), version 31250 (fail), versions, 15625, 7812, 3906, 1953 and 976. Now suppose that version 7 compiles version 976 successfully. So the failure with version 7 is between 976 and 1953. But since version 976 is stronger, you can start working forward with version 976. So it's like a binary search that's restarted whenever you get a "greater-than". Even if for some reason this were a manual process, each time you get a working version you at least halve the remaining space. Finally, as you said above, someone could make a batch file / shell script that literally goes through every commit in the version control system (not skipping any) and always use the previously working version on the next working version. A script doing so may well run in matter of days, though, depending on how long it takes to compile a the compiler compiler. Ordinarily there are a lot of commits! The binary search above cuts this down significantly. (However the binary search isn't theoretically guaranteed to be faster; after all theoretically we can imagine that version 7 compiles version 8 but fails on version 9; version 8 compiles version 9 but fails on version 10; etc. So theoretically every single commit could be breaking. (Theoretically.) But that's extremely unlikely to be the case. I don't imagine you'd have to do more than a few hundred compilations with the above binary-search methodology before you got one that started with version 7 but stepping through the commits in the way specified, produced a binary that compiles the latest version. The process may have to be partly manual due to breaking changes in semantics of invoking the compiler or its dependencies, but that should be rare. This process would also in the end allow you to do a bit-for-bit comparison of the output of the current version of the compiler when compiled using the above trusteable version, versus compiled from source code with the "trusting-trust" backdoor (where every version is backdoored and inserts a backdoor when compiling itself, without this backdoor being in the source code anywhere. so the above process would let you tell whether there's a trusting-trust backdoor, as long as there is a single early version that for sure didn't have it yet, and you have the commit history (from which the trusting-trust has been edited out). as I said above, if you don't have a single known-good version without the trusting-trust backdoor, then you'll have to write something that can compile version 2 or 3 (or 7) yourself, in another language.
- Manishearth 10y ago
  I did get that they were placeholders :) I just wanted to note that the scale was way off. You said "I wouldn't expect a the 2012 rust prerelease to .." followed by "but it can probably do 2013", so it was clear you had an expectation of what the dates would be approximately like. And for many compilers, this is true -- you can use really old compilers to compile the new one. But not everyone is aware of how tumultuous Rust's history is, so I thought it interesting to note. I should have worded it better I guess.
  - logicallee 10y ago
    yeah I was just trying to illustrate what I meant, like, the process. And you're right, I didn't know it was so tumultuous so with your clarification it's an interesting observation :) (By comparison the specifications for C don't break earlier compilers often at all.) Thanks for the clarification :)

by vog 10y ago

logicallee 10y ago

yes. I'm pretty shocked Manishearth didn't get that I was just giving examples of the process with placeholder dates, since I started my comment explicitly stating (I add emphasis here): >you use an old compiler binary that didn't have the attack yet to compile the latest source code that it is able to compile, then use that to compile the latest it can compile, and so forth. in trying to find the "latest source code that it is able to compile" you can do a binary search backward from the current version of the source code. it doesn't take long to find the latest version for each one (i.e. the latest each one compiles without error, into a working binary that passes some test suite). And anyway whenever you're binary-searching forward (i.e. after any point where the binary search yields ""greater-than" because the one you just tried compiled) then you can just use the version you just successfully compiled. Let me illustrate what i mean with this binary search: so if we're at version 1 million today, which the version 7 doesn't compile, then you try version 7 on version 500,000 (it'll fail), then on version 250,000 (it'll fail), version 125,000 (it'll fail), version 125,000 (it'll fail), version 62,500 (it'll fail), version 31,250 (it'll fail), version 62500 (fail), version 31250 (fail), versions, 15625, 7812, 3906, 1953 and 976. Now suppose that version 7 compiles version 976 successfully. So the failure with version 7 is between 976 and 1953. But since version 976 is stronger, you can start working forward with version 976. So it's like a binary search that's restarted whenever you get a "greater-than". Even if for some reason this were a manual process, each time you get a working version you at least halve the remaining space. Finally, as you said above, someone could make a batch file / shell script that literally goes through every commit in the version control system (not skipping any) and always use the previously working version on the next working version. A script doing so may well run in matter of days, though, depending on how long it takes to compile a the compiler compiler. Ordinarily there are a lot of commits! The binary search above cuts this down significantly. (However the binary search isn't theoretically guaranteed to be faster; after all theoretically we can imagine that version 7 compiles version 8 but fails on version 9; version 8 compiles version 9 but fails on version 10; etc. So theoretically every single commit could be breaking. (Theoretically.) But that's extremely unlikely to be the case. I don't imagine you'd have to do more than a few hundred compilations with the above binary-search methodology before you got one that started with version 7 but stepping through the commits in the way specified, produced a binary that compiles the latest version. The process may have to be partly manual due to breaking changes in semantics of invoking the compiler or its dependencies, but that should be rare. This process would also in the end allow you to do a bit-for-bit comparison of the output of the current version of the compiler when compiled using the above trusteable version, versus compiled from source code with the "trusting-trust" backdoor (where every version is backdoored and inserts a backdoor when compiling itself, without this backdoor being in the source code anywhere. so the above process would let you tell whether there's a trusting-trust backdoor, as long as there is a single early version that for sure didn't have it yet, and you have the commit history (from which the trusting-trust has been edited out). as I said above, if you don't have a single known-good version without the trusting-trust backdoor, then you'll have to write something that can compile version 2 or 3 (or 7) yourself, in another language.

Manishearth 10y ago
I did get that they were placeholders :) I just wanted to note that the scale was way off. You said "I wouldn't expect a the 2012 rust prerelease to .." followed by "but it can probably do 2013", so it was clear you had an expectation of what the dates would be approximately like. And for many compilers, this is true -- you can use really old compilers to compile the new one. But not everyone is aware of how tumultuous Rust's history is, so I thought it interesting to note. I should have worded it better I guess.
- logicallee 10y ago
  yeah I was just trying to illustrate what I meant, like, the process. And you're right, I didn't know it was so tumultuous so with your clarification it's an interesting observation :) (By comparison the specifications for C don't break earlier compilers often at all.) Thanks for the clarification :)