What I learned from my first C coding challenge • Hacker News Board

Re: What I learned from my first C coding challenge

#21

Post by Keyframe » Tue, Sep 04, 2012, 7:36 PM UTC

twoodfin wrote: post #11

jparishy wrote: post #9

As a note to the author about separating the arrays instead of using a structure, it was probably an alignment issue? Check out http://en.wikipedia.org/wiki/Data_structure_alignment

More specifically, a pointer in x86-64 (and most other 64-bit architectures) is going to be 8-byte aligned, which means that a struct of an 8-byte pointer plus a 2-byte short will actually consume 16 bytes. Alternatively, keeping them in separate arrays removes the alignment overhead, and each pair of values will consume 10 bytes. That's a substantial savings when you're trying to fit into something like a 32KB L1 da…

AoS vs SoA strikes again?

Re: What I learned from my first C coding challenge

#22

Post by tptacek » Tue, Sep 04, 2012, 7:37 PM UTC

masterzora wrote: post #19

tptacek wrote: post #15

Earlier quoted context omitted.

A timing attack against URL query strings as processed by a normalizing cache proxy?

Quoth the parent: "It does not apply here"

Sure. The flaw here isn't strcmp. In fact, most crypto compares don't use strcmp, even in naive code; an HMAC-SHA1 MAC, for instance, is an array of 8-bit bytes, not the hex string that programs encode them into for human consumption. "memcmp" is the normal culprit.

Timing attacks aren't a flaw in memcmp or strcmp. Touching every byte of a string is stupid behavior in the overwhelming majority of cases.

Re: What I learned from my first C coding challenge

#23

Post by tptacek » Tue, Sep 04, 2012, 7:39 PM UTC

jparishy wrote: post #20

tptacek wrote: post #17

Earlier quoted context omitted.

No, strcmp is not susceptible to buffer overflow attacks.

https://buildsecurityin.us-cert.gov/bsi-rules/home/g1/847-BS... If passed an unterminated string, the function will fail at least. How much you could exploit from that, I guess I exaggerated.

That's not a buffer overflow.

This whole subthread of picking on the guy's implementation because of "strcmp" is pretty silly. There are times where strcpy() is safe to use, but most of the time it's a red flag. There are conceivably times when strcmp() is unsafe to use, but to a professional reviewer, it is very rarely a red flag.

I should have just come right out and said that, rather than begging for the rationale for picking on strcmp().

Re: What I learned from my first C coding challenge

#24

Post by jasonmoo » Tue, Sep 04, 2012, 7:42 PM UTC

kstop wrote: post #18

We're getting ready to deploy Varnish in (non-devops) work. Not having control over production and having the potential for C inline in the config was already making me a bit nervous. This thread is not helping!

Varnish has actually been a great tool for us. The 3rd party url-sort plugin that we tried was not. Had a memory leak that caused the server to crash periodically. Once the url-sort module that we're building as part of this code challenge is tested and fully formed we'll make it available as open source.

Re: What I learned from my first C coding challenge

#25

Post by adsr » Tue, Sep 04, 2012, 7:53 PM UTC

jparishy wrote: post #6

tptacek wrote: post #4

Earlier quoted context omitted.

Reading strcmp() makes you think "security hole"? Why?

It doesn't take the length/amount of characters to compare as an argument relying on the null terminator, meaning it's susceptible to a buffer overflow attack. Moral of the story, if you're going to use C strings, use the strn* variants.

I prefer strcpy to strncpy, and make sure that the string will fit before the call. I use strncpy if I want to copy n characters from s2 to s1, strncpy can give a false sense of security imo since it may not add a terminating zero, for example using strncpy with strlen. The BSD strlcpy does always null terminate the string, but it's non standard.

Re: What I learned from my first C coding challenge

#26

Post by iopuy » Tue, Sep 04, 2012, 8:00 PM UTC

Nice, i remember my first coding challenge in c. Nice result for first attempt.

Re: What I learned from my first C coding challenge

#27

Post by Xuzz » Tue, Sep 04, 2012, 8:08 PM UTC

tptacek wrote: post #22

masterzora wrote: post #19

Earlier quoted context omitted.

Quoth the parent: "It does not apply here"

Sure. The flaw here isn't strcmp. In fact, most crypto compares don't use strcmp, even in naive code; an HMAC-SHA1 MAC, for instance, is an array of 8-bit bytes, not the hex string that programs encode them into for human consumption. "memcmp" is the normal culprit. Timing attacks aren't a flaw in memcmp or strcmp. Touching every byte of a string is stupid behavior in the overwhelming majority of cases.

Unless, of course, you're Nintendo: http://wiibrew.org/wiki/Signing_bug

Re: What I learned from my first C coding challenge

#28

Post by tsahyt » Tue, Sep 04, 2012, 8:10 PM UTC

It's interesting that he points out that testing for zero is cheaper than comparing two numbers. Interesting because this might not always be the case.

For a quick test I used the conditions (i=0; i And this is where it gets complicated. This optimization depends entirely on the inner workings of the ALU. Theoretically one can test against zero with just one subtraction, because 0-n == n-0 is always true, whereas a-b == b-a iff a == b, otherwise the two sides will differ in sign. On a hardware level such operations might be parallelized inside of the ALU though, so a comparison of two numbers might actually take exactly as many clock cycles as the comparison against zero.

It's however an interesting excursion into how such basic things work. And concerning my test: They're both about equally fast on my machine. I've done multiple runs with no clear winner.

Re: What I learned from my first C coding challenge

#29

Post by icefox » Tue, Sep 04, 2012, 8:18 PM UTC

Any more detailed information about the coding challenge?

For example the repo references a 5Murls.txt file, but it isn't part of the repo and the blog says it needs to "output in a standardized format:", but doesn't specify what "standardized" means nor does the current code actually output anything (the printf is disabled). Does it specifically need to go to stdout or just that it exists somewhere in memory? Does it require a char* or will this char* be instantly hashed and tossed away? Does the challenge forbid the use of threads/cpus/workers? In the blog it says: "In this particular context the plugin architecture we were writing against allowed for returning the original string or a new malloc’d string" Are you allowed to muck with the original string? In the code on github it has a function that takes a const char* forcing a malloc, but it could easily just re-write the string in place if allowed.

edit: As for sorting the params, (based upon your comments about the common usage) pretty sure there is a way to do this without any string comparisons at all. Post a sanitized 5Murls.txt file and give it a go to make a patch.

Re: What I learned from my first C coding challenge

#30

Post by comex » Tue, Sep 04, 2012, 8:19 PM UTC

The hand rolled strcmp almost certainly performed better than the native one merely because it can be inlined; consider using rep cmpsb or directly including another assembly version of strcmp (though since the strings are short the latter's overhead might not be worth it). Ditto memcpy.

Perhaps also consider using a radix sort?