Thoughts on the Automata Course I took

Jeffrey Ullman's Automata course is very interesting, but heavy on the pea counting effort, and I have no pigeons handy that could help me out here, and this guy here isn't lending me his crew:

Still, it's a worthwhile class to take even if using n tracks on the Turing machine felt a little bit like cheating.  And the 3-SAT concept is useful to know in general too, and whilst I was struggling with some of the topics, it did give me a good workout.  Well, if it would be easy, it would not be so useful, no? ;-)  I definitely would not claim I understand the topic, but I gained an appreciation, and learned where to look in case I ever need it.  And I plan to retake the course if it runs again.

I did buy the Introduction to Automata Theory, Languages and Computation for ~£5 second hand, but it's a lot to read and going through it will take some time (a paragraph a day will eventually get it read, it's the Turing Machine method of studying -- it may or may not complete)

As a bonus, Mr. Ullman used a free version of his Foundations of Computer Science book, which is a very nice scenic tour of general CS concepts and a great way of refreshing long forgotten topics and picking up a few new ones.

My Buffer Overflowesth

There I was,  looking for a video on the glibc malloc implementation (more about that adventure in the next post) and whilst the most promising clip I found was unfortunately in Japanese (and, it has to be admitted, this is about as much as I currently understand about this topic :-)  --- I came across a gentleman on the sidebar who posted a nifty video series about buffer overruns,  and who has a good way of explaining the problem.

If you've always wondered just exactly how a buffer overrun works in real life(in a very basic way) check his video series out {some basic assembler required}:

So much for productive procrastination ;-)

Part  2, 3, 4, 5, 6, 7, 8, 9

Solving a Non-Problem

If you solve Euler Project problem 26, you will be able to see my 'solution' in the forum for that problem on page 9, as user Gabriela.

It's terrible.  Taarrrribbble.   First I didn't research the math, thinking: Oh, that is _easy_!  Then one simple hack led to another quick hack (with a bit of faerydust sprinkled) and let's just say I got the correct solution the first time I checked, because I lucked out, not because I wrote a good algorithm.

Valgrind was happy with it.  I'm not.  After posting the code, I realised that *somehow* I crammed nearly 1000 chars into a string I malloc(500)'ed.

The question is:  Why did it work?  The next question is: would it work on another computer?  And most important of all: should it have worked in the first place?  Plus, other than eye balling the code and seeing the obvious problem, is there a way to check?

True, you could say that it's not a bug as such, because it does what I intended, but... the issue that I have, is if that isn't picked up with a nice helpful (and popular!) SIGSEV, what else is as dodgy and wrong?

Adding -fstack-protector-all didn't help to find a indication of an error either.

After some surfing, I found that dmesg (and readelf -s) is my friend, and, lo and behold:

(...)
[12556151.546186] project2-exe[18950]: segfault at 7fff5a18ae00 ip 00007fd452916744 sp 00007fffaddf9338 error 4 in libc-2.19.so[7fd45288d000+1bb000]                                                                       
[12564217.667780] traps: project2-exe[19250] general protection ip:7f94a50ad7cd sp:7fff01927b90 error:0 in libc-2.19.so[7f94a5072000+1bb000]
(...)         

Luckily I knew where the problem was, or so I thought.  But, alas, this was a previous SIGSEV which I had fixed[1] and there was nothing that readelf had to tell me.  After some more coffee, I finally had the bright idea that perhaps those allocations were just not used, and I checked the man pages for strndup() and strstr() and... yep, that was the non-problem.

[1] One good reason to use the emacs shell instead of M-x compile:  search upwards is trivial and you find out some things that otherwise would have confuzzled you for yonks.