Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

boring C compiler

Name: Anonymous 2015-12-21 20:22

https://groups.google.com/forum/m/#!topic/boring-crypto/48qa1kWignU

this site requires javascript to view.. it's a fucking plain text message.. anyway:

14:40 D. J. Bernstein
As a boring platform for the portable parts of boring crypto software,
I'd like to see a free C compiler that clearly defines, and permanently
commits to, carefully designed semantics for everything that's labeled
"undefined" or "unspecified" or "implementation-defined" in the C
"standard". This compiler will provide a comprehensible foundation for
people writing C code, for people auditing C code, and for people
formally verifying C code.

For comparison, gcc and clang both feel entitled to arbitrarily change
the behavior of "undefined" programs. Pretty much every real-world C
program is "undefined" according to the C "standard", and new compiler
"optimizations" often produce new security holes in the resulting object
code, as illustrated by

https://lwn.net/Articles/342330/
https://kb.isc.org/article/AA-01167

and many other examples. Crypto code isn't magically immune to this---
one can easily see how today's crypto code audits will be compromised by
tomorrow's compiler optimizations, even if the code is slightly too
complicated for today's compilers to screw up. A boring C compiler will
eliminate these nasty surprises; it will prioritize predictability.

I should note that this plan, throwing away gcc and clang in favor of a
boring C compiler, isn't the only possible response to these types of
security holes. Here are several other responses that I've seen:

* Attack the messenger. "This code that you've written is undefined,
so you're not allowed to comment on compiler behavior!" The most
recent time I saw this, another language lawyer then jumped in to
argue that the code in question _wasn't_ undefined---as if this
side discussion had any relevance to the real issue.

* Say that the C "standard" allows gcc and clang to do whatever they
want to all of these "undefined" programs. Yes, we know that it's a
stupid "standard"; that isn't the question. What do we do about the
resulting security problems?

* Blame the security holes on the C programmers who wrote "undefined"
programs. This _might_ be reasonable if there were a plausible plan
to reduce the fraction of "undefined" programs from ~100% to ~0%,
but there isn't. Even if there were, how would this massive code
revision be better than keeping the code and switching to a boring
C compiler?

* Claim that earthquakes in the behavior of "undefined" programs will
teach C programmers to stop writing such programs. "That'll show
'em!" But the reality is that this hasn't worked and won't work.

* Claim that all we need is for some particular "undefined"-catching
tool to be widely used. In fact, these tools are full of false
positives and false negatives; at best they catch a few limited
types of "undefined" behavior, not changing the big picture.

* Claim that a boring C compiler can't possibly support the desired
system _performance_. Even if this were true (which I very much
doubt), why would it be more important than system _correctness_?

Overall I think that these people simply don't understand what most C
programmers want. A boring C compiler will very quickly gain users---not
merely for security but also for predictability in general; people will
appreciate, e.g., having variables automatically initialized to 0. Of
course, the compiler has to support the usual C ABI, so that programs
compiled with this compiler can be linked to libraries compiled with
other compilers (including other languages), and vice versa, allowing an
incremental upgrade process.

I'm told that the Plan 9 compiler tries to be somewhat predictable---

http://article.gmane.org/gmane.os.plan9.general/76989

---but it still leaves many things unspecified, and I'm under the
impression that it has its own ABI. There's a "Fail-Safe C" compiler
that sounds like it defines much more, including safe semantics for
buffer overflows---

https://staff.aist.go.jp/y.oiwa/FailSafeC/index-en.html

---but it's clear that this has its own ABI. There are various projects
such as

http://www.doc.ic.ac.uk/~awl03/projects/miro/

that add more useful semantics to some parts of C _without_ changing the
ABI, but the same compilers will happily screw up other parts of C.
There's a "Friendly C" proposal that targets other parts of C more
relevant to core crypto---

http://blog.regehr.org/archives/1180

---but the big picture is still tons of misguided flexibility for the
compiler writer.

---Dan

Name: Anonymous 2015-12-31 4:05

>>80
umad cunt?
this is /prog/, it was born on 4chan

Name: Anonymous 2015-12-31 4:41

>>77
You're still in the realm of specific per-algorithm custom tests, not a single general solution. IE, you don't know what the fuck the halting problem even is.

Name: Anonymous 2015-12-31 4:49

>>82
There is no general solution to the halting problem (at least on infinite input sets), that is true. It is not that type of problem. No one disputes this.
It has been claimed in this thread that the halting problem does not apply at all to finite programs over a finite input set. You are the only one disputing this.
In this thread, you have been proven wrong, and it has been shown that your claims are irrelevant.　　　　　＼＼＼　　　　　 　　,,..-‐''''￣｀゛""''‐..、　 　 　/｀i　,-,
　　　　　　　　　　　　　 r-､／,..-‐''''￣｀゛""''‐､　 ｀ヽ､ /｀i　ﾚ'　/-,
　　　　　　　　　　　　く｀i　ン 　　　　　　　　 ､　ヽ　 　 i　 ヽ　　＜_
　　　　　　　　　　　　 Lｙ´/ 　i　　 ﾊ 　!∠ 　　',　ヽ　　〉　　 ノー'´
　　　　　　　 ,-､　　　　ｲ　i　 ﾊ､_ﾚ' ﾚ!,ｨ'´｀ﾊ､_.!　i 　! /　　/
　　　　　,..--＼ ヽ､　　 Ｌ!_ﾊ_!rrヽ,　　´ﾋ__ノﾉ L_ﾊ__!./　　,'!
　　　　　_＞　 ,.---'ヽ.　　/ ﾊ'ﾊ_ﾘ　　　　　 "　/ ﾊ /　　 ,'.|
　　　　 ｀ー-, ｀ー-　´＼ !. / !"　　r'"⌒ヽ 　/　 ,./　　 /　|
　　　　　　'ｰ-^'ー' ､　 ｀r'´レへ､　ヽ 　__,ﾉ　ﾚ／､ゝ--"ﾊﾉ
　　　　　　　　　　　　＼ !､.　 　ヽ＞r‐r=ﾆﾝ/　 　　￣　 !
　　　　　　　　　　　　 !ン ､　　,.ｲ /}><{　　ハ　　　 　　/
　　　　　　　　　　　　　｀､　　　/　　Ｙ 　〒　 L｀､____／
　　　　　　　　　　　　　　 ｀ｰ／　　　i ：　　　 　　!　

Name: Anonymous 2015-12-31 4:50

Also, this thread needs more cuteness. It has gotten far too angry. 　　　　　　　　　　　　　　　　　　　,.-‐‐､　　　　　,.-‐-､
　　　　　　　　　　　　　　　　　　_,.i　（ﾉ::）i--‐‐‐'7　（ﾉ::）
　　　　　　　　　　　　　　　　r''´　ゝ､ 'ｰ'ﾉ　　　　ヽ、 ｰ'ﾉ
　　　　　　　　　　　　　　　 /　　　　 ￣　　　　　　　￣':,
　　　　　　　　　　　　　　／　　　　　　　　　　　　　　　　ヽ,
　　　　　　　　　　　　,,r'´　　　　　　　　　　　　　　　　　　　' ､
　　　　　　　　　 ,.ｨ''" ___＿,, -‐ ─‐ ''"´￣￣￣￣￣｀゛ー‐-二ｽ、
　　　　　　　　,<-‐''"´/ , '　 , '　 /　 ,'　　/ 　/X',　 !　 ',　 ':,　｀ヽ;::｀ﾞ'':、
　　　　　　　 '､:::::::::::::,' /　 /　　,' , -ﾅ‐-､　 ,'　　 i　_i_　i　　 !　　 !::::::::ﾉ
　　　　　　　　 ｀ ﾞ ''ｰ! i 　 !　　 i　　ﾉ_｣__ﾊ　!　 　 !'/i ｀ﾊ,　　i　　 i-‐'´　　　　　　　 ＼ | ／
　　　　　　　　　　　　l l　　!　　 l｀ｧ'´ ,´ﾊ｀ヽ!　　 ,ﾚ'=ﾅ'､i.　 ,i　　 !　　　　　　　　　 ─ ○ ─
　　　　　　　　　　　　i i　 ﾓ, 　 ﾊ ! 　 !ﾉ i　　　　　i ﾉi　 !l　/i　　,'　　　　　　　　,. 　 ／ | ＼
　　　　　　　　　　　 / i　ﾘﾔ'、 ﾊ　　　ゝ'　　　　、 '､ｿ　 ,ﾚ',. !　/　　 ,:'⌒ヽ､_,.ノ
　　　　　　　　　　 ノ　 ﾚ' ハ ヽ!. ',　""　　,. ‐‐-､　　""i､_)　ﾚ'
　　　　　　　　　,'´　　　　_｣　　i　 !　　　　'､　　ｿ　　　,ﾊヽ　|
　　　　　　　　 ,'　　　 ,:'´:::｀L　l　 ﾄ ､..　　　　　　,.. イ i　!　　',
　　　　　　　　 i　　　,':::::,ｨ´｀:､L､i　'r､ ｀゛ｰ - r''ｽ,　 l　! /　!　）
　　　　　　　　 ﾚ'´!ﾍ7:::/　　　 ヽ,ヽ_i::ヽ､ ___,.ﾉ:::∩,ﾍi_/´ iノﾚ'
　　　　　　　　　　 ,.':::::::i　　　　　 ',::::::::::::::::::::::::ﾉ i
　　　　　　　　　　/:::::×l　　　　　 ',::::::::::::::::::::/　｀i
　　　　　　　　　 /:::::×::｣_　　　　　i::::::::::::::::::,'　　 !
　　　　　　　　 _,':::::,:'´　　 ｀ヽ,　　　｀i:::::::::::/　　　Y'''‐-､
　　　　　　 _｣´:::::::/　 y　　　　',　　 ﾉ､:::::::〈　　　 ｲ　　　ヽ
　　　　　／:::::::::::,:'　_/　　　　　!　　　 |::::::/｀　 　 i´　　　/
　　　　　`ヽ､:::::/　/ ｀゛ｰ- ､__,'　　　　｀i:::i　　　　 l｀゛ｰ- 'i
　　　　　　/:::V　 ,'､　　　　　 ﾉ　　　　 ｀V　　　　 ﾄ､ ___ ﾉ
　　　　　i´:::::〈　 ,'　`ー- ､__/　　　　　　 l　　　　 i 　 ,'
　　　　ノ:::::::::::｀i i　　　　　,ﾒ､　　　　　　　',　　 　 ',　,'
　,.ｨｰ'´::::::::::::::::ﾉ !　　　　/::::i ｿ　　　　　　 i　　　　｢⌒i
　ヽ､,::::::::::::::::::(_ｽ､_/´⌒〈::::ﾉ　　　　　　 　 ':,　　　｀V´ﾝｰ-､
　　　`ー､_＿,.ｲ:::::::｀ー-'｀ヾ､　　　,ｧ‐'´｀ヽ､ﾉ'⌒ヽ､,｀i::::::::::::i
　　　　　　　　 !､__::::::::::::::::::::::）　 ,ｲ__,__,__ｨ_ﾒ､ｧ,__,_,_,)ﾒ--‐'´

Name: Anonymous 2015-12-31 5:26

>>83
Harken back to >>51. It is not a practical, tractable problem even with finite inputs.

Given that the analysis machine has infinite memory and time to track the full-state simulation of the target program + inputs, it could go full brute force and search for repeated states of a finitely bounded target machine.

None of that matters or makes any kind of sense with statically analyzing undefined behavior.

Name: Anonymous 2015-12-31 13:10

>>69,73,77

Your problem is that you're mentally retarded (or literally like 13) and unable to understand the difference between unbounded and infinite. It's obvious when you say stupid shit like "The halting problem is only concerned with infinite machines" -- yeah, sure, and Goldbachs conjecture is only concerned with infinite natural numbers. Wait, there's no such thing as an infinite natural number, is it? The only infinite thing here is your stupidity, isn't it?

Name: Anonymous 2015-12-31 14:23

wanted to talk about boring c
sophmores shitting up the thread explaining their recently aquired knowledge of turing machines

bad feels mane tbh

Name: Anonymous 2015-12-31 16:39

>>87
Who are you quoting?

Name: Anonymous 2015-12-31 17:02

>>86
Turing machines are infinite machines.

Natural numbers are all finite by construction, Turing machines have no such restriction. The tape is unbounded, giving it an infinite amount of memory, meaning it can work forever. If it only had, say, 16G tape entries, it woulf have to either halt having completed or halt after exausting all 16B entries when meaningful compuation is no longer possible. It will not run forever.

Name: Anonymous 2015-12-31 17:50

This thread will halt at >>1000. Thank fuck!

Name: Anonymous 2015-12-31 18:45

I would just like to note that proofs of halting are pretty useless because even a halting procedure may take thousands of years to complete in which case it will be practically indistinguishable from a calculation which never halts.

The job of an algorithm designer is to make an algorithm which takes provably practical time to complete, not to prove whether it halts or not. The former is a useful property, the latter is useless even if proven.

Name: Anonymous 2015-12-31 19:41

>>91
An algorithm, by definition, must provably halt. If it does not, it is a program.

Name: Anonymous 2015-12-31 19:50

>>91
you're a fucking idiot

Name: Anonymous 2015-12-31 19:51

Quoting <http://bbs.progrider.org/math/read/1428099144>:
[...] don't make programs that fucking write themselves. Problem solved. Same goes for other programs: don't make programs that suddenly loop forever and your shitty self-referencing program won't be a contrived edge case for which Halt(p, input) doesn't work.

Name: Anonymous 2015-12-31 20:05

>>92
Obviously. But proving that it's an algorithm is useless in practice. Only proving that it's an algorithm which takes a bounded and reasonably low amount of resources to complete that counts. Would you use a Fibonacci algo which has been proven to terminate but takes 3 years to calculate the 1000th term?

>>93
No, you.

Name: Anonymous 2015-12-31 22:05

tfw board is full of retards

Name: Anonymous 2015-12-31 23:45

>>95
You have to prove it halts to find the time and space complexity anyway.

Name: Anonymous 2016-01-01 10:07

>>97
As a useless side product, yes.

Name: Anonymous 2016-01-01 10:51

This thread has halted peacefully.

Name: Anonymous 2016-01-01 17:30

>>89
Turing machines are infinite machines.

Natural numbers are all finite by construction, Turing machines have no such restriction. The tape is unbounded, giving it an infinite amount of memory, meaning it can work forever.

And each instance of a TM either stops in a finite number of steps or doesn't stop at all. Its run time is not an "infinite natural number".

Asking "does this TM stop" (when started on an empty tape, eliminating input doesn't matter) is not different from asking "Can every natural number be represented as a sum of two primes". The latter statement obviously doesn't involve any "infinite natural numbers". And the former statement is obviously so very not different from the latter than you can go and straightforwardly encode one as another.

In each case we are not talking about any "actual infinity", we are only talking about unbounded finite numbers, is some finite number not representable as a sum of two primes? Does this TM stop after some finite number of steps?

>>99 nice dubs.

Name: Anonymous 2016-01-01 20:03

>>100
There are no instances of Turing machines because infinite memory storage does not exist.

Name: Anonymous 2016-01-02 2:12

>>94
What's the point of programming if not to make programs that write themselves? Anything less is just shit tinkering.

Name: Anonymous 2016-01-02 14:12

>>101
TMs don't need infinite memory, only unbounded ;-)

Name: Anonymous 2016-01-03 3:03

>>103
you're a retard

Name: Anonymous 2016-07-18 15:42

>>103
What's the difference in practical terms?

Name: Anonymous 2016-07-18 18:08

The U.S. government and Lisp community spread C because it makes computing worse.

Nobody would even look at Lisp machines if we all used an iAPX 432 or similar computer.

The Lispers couldn't even compete with what people were using before. There is no way they could have competed with the capability-based computers that were being designed in the late 1970s. They believed the only way to popularize Lisp was to kill everything that is better.

Even the best of the Goyim should be killed.

Name: Anonymous 2016-07-18 23:37

>>105
Unbounded exists, infinite does not.

Name: Anonymous 2016-07-18 23:56

>>107
Show me a computer with unbounded memory.

Name: Anonymous 2016-07-19 0:55

>>108
Because of virtual memory and other paging games that can be done, practically all of them. All that needs to exist is an interface to memory, as all of this is at the conceptual layer. Something niggers like you repeatedly fail to grasp and always convolute with physical systems.

Name: Anonymous 2016-07-19 1:01

>>109
Even with virtual memory, you still need somewhere to put the data. If your system has say A bits of RAM, B bits of hard drive storage, C bits of removable disk storage, D bits of processor registers, your system has only 2^(A+B+C+D) possible states. Which means it's equivalent to a finite state machine, not a Turing machine.

Name: Anonymous 2016-07-19 3:27

(this post left intentionally blank)

Name: Anonymous 2016-07-19 3:28

>>110
There's no limit to the "somewhere". You can keep adding storage devices to a computer, and more computers to that computer via network. It's not bounded.

Name: Anonymous 2016-07-19 4:05

>>111
DAMN YOU

>>112
For a non-networked machine, there's a limit to how much storage is available until you physically modify it by adding more devices. And even with networking, the space available is still bounded.

Suppose every storage device in existence is already filled to capacity. The total data stored is a bounded quantity, however there still isn't room to add anything more. So the total storage capacity is still bounded.

Name: Anonymous 2016-07-19 7:21

>>113
That's not what bounded means, and you know it. Or you don't know it, and need to kill yourself.

Name: Anonymous 2016-07-19 7:53

>>114
Okay, smart guy, what does bounded mean, and how can a quantity be finite, yet unbounded?

Name: Anonymous 2016-07-19 12:21

Check em dubs

Name: Anonymous 2016-07-19 13:04

>>114
The depth of your anus is unbounded.

Name: Anonymous 2016-07-19 14:45

14:40 D. J. Bernstein

Actually this is an impostor from an alternate reality. The real DJB's surname has always been Berenstain.

>>115
They'd teach you that in high school, after all required prerequisites. It's pointless to waste time on you before that.

Name: Anonymous 2016-07-19 15:35

>>115
I've taken college level calculus courses and they only barely touch on the concept of infinity (mostly in the context of limits/end behavior of functions). Regardless, the data storage available in the real world is bounded, because it is possible to add up all the data storage media in the world and you'd get a specific quantity. If you're going to claim computers today have unbounded memory, at what point in history did their memory cease to be bounded? In 1945, the total memory of all computers in the world was way less than one terabyte. Are you seriously going to claim that "less than one terabyte" is an unbounded quantity?

Name: Anonymous 2016-07-19 15:45

>>119
Meant to reply to
>>118
Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode + RSS -