Bug zapper? :)

(Assuming this accurately falls under [RFC]; I *am* requesting comments on this method)

A pondering of all the bugs in the linux kernel-- and yes, we all know there are bugs, stable or not-- always leads me to attempt to figure a way to get rid of them. In the past I'd thought of taking just an unstructured "Tell the list to take a month to try and kill all bugs" approach; but decided that that would be a rediculous idea. Since then I've been pondering, trying to figure a good and reliable way to do it other than rewriting from scratch (a very effective method of delousing a huge codebase).

I recently read a few pages in a book on exploiting software, skimming it in the bookstore to see if it was worth the buy. For those interested, it's ISBN 0201786958, "Exploiting Software: How to Break Code." This gave me some insight into possible solutions.

The book covered several exploit types, although it didn't seem from the glance I took to indicate strong separation between those that exist by design (the ILoveYou bug used this type) and those that exist by screw-up (MSBlast and Sasser used these). It discussed typical buffer overflows and software bugs, though.

What I found interesting was that it described bugs as pseudo-quantitative based on the KLOC (thousands of lines of code) for a code body. The basic theory boils down to 5-50 bugs per 1000 LOC, approaching 5 for QA audited code. Thus, 10000 LOC executable, 50 bugs.

Decrease the size of the code body, and you evade the above issue: A small, independent code body will have the number of bugs approach 0; fractional (less than one) bug counts are lost. This can be realisticly done.

First, above every function's implementation, explain the function in terms of **input**, **output**, and **state change**. Detail its **process** as well if possible. This allows you to make a definite review of a function from wherever you call it, simply by reading the comments.

Second, in all of your code, assume that the functions you call do **exactly** what these comments say they do, no more, no less. This takes your view off the worry of "will this do something unexpected" and moves it to "am I screwing up HERE?" This narrows your code body to the current function for the brief period that you're writing it.

In passing, you can check a function for bugs while considering it only the process that it performs, and puting absolute trust in the functions that it calls. By explaining the process it performs, everyone else who looks at the code has deep enough knowledge that they can see bugs if they have technical knowledge about coding and the other functions. Furthermore, large code bodies are reduced to small sets of logical processes-- each function effectively becomes ONE line of code.

The result is that you micro-manage your functions, causing related bug searches to be narrowed down to them with confidence that your understanding of the function is correct due to the explaination above the function body. This reduces all code bodies (asside from assembly) to a handfull of LOC, which statistically should have 0 bugs.

In practice, I believe this high volume of documentation will not reduce the kernel's bug count to 0; however, it would become closer, I believe.
It would become especially easier to devout bug-hunters, who no longer
have to take several days to understand the code.

What do you all think? Do you see flaws in my logic?

--John

All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

Sorry, 64 bit cpu, Thunderbird is broke so no enigmail.  I'd sign it if I could.

[...]

Oh, no; as I said, even heavily quality assurance audited code has maybe 5 bugs per kloc. Where do the mremap() and munmap() bugs come from? Obviously you guys don't get everything.

Just do it in passing; you don't have to put a sudden hard effort to do these things in. It'd be nice, but a major undertaking.

What I'm suggesting isn't much though, is it really? Consider the functions function (normal code, not necessarily kernel):

void get_food(char **a) {
*a = malloc(strlen(global_food) + 1);
strcpy(*a, global_food);
}

/*Set our food*/
int set_food(char *food) {
if (!food)
return -1; /*error*/
free(global_food); /*if NULL, nothing happens*/
global_food = malloc(strlen(food) + 1);
strcpy(global_food, food);
return 0;
}

You'll have to forgive the lack of formatting; thunderbird is mean about this :/

Anyhow, as you can see, these are quite simple. Function names are self-eplanitory, as is the process. Assumedly, these are fine.

Now, we could try another approach at this, below.

/* get_food(char **a)
* Gets the current food.
*
* INPUT:
* - char **a
* Pointer to a pointer for the outputted food.
* OUTPUT:
* - Return
* none.
* - *a
* Set to a copy of the current food.
* PROCESS:
* - Set '*a' to a newly allocated block of memory containing a copy
* of the current food (global_food)
* STATE CHANGE:
* none.
*/
void get_food(char **a) {
*a = malloc(strlen(global_food) + 1);
strcpy(*a, global_food);
}

/* set_food(char *food)
* Sets the current food.
*
* INPUT:
* - char *food
* Pointer to an ASCIIZ string containing the new food
* OUTPUT:
* - Return
* -1 on error
* 0 on success
* PROCESS:
* - If (food is NULL)
* - return error (-1)
* - If (food is not NULL)
* - Free current food (global_food)
* - Set current food (global_food) to a newly allocated block
* of memory containing a copy of 'food'
* STATE CHANGE:
* - current food (global_food) is set to 'food'
* - Memory holding previous food is freed
*/
int set_food(char *food) {
if (!food)
return -1; /*error*/
free(global_food); /*if NULL, nothing happens*/
global_food = malloc(strlen(food) + 1);
strcpy(global_food, food);
return 0;
}

These comment blocks are *MUCH* more verbose. They describe the process loosely, but do give enough information to allow understanding without questions.

The large amount of extra commentary is worth it, IMHO.

All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

This is a typical coding problem:

- no comments are better than wrong comments
- code which is understandable w/o comments is better than commented code

And of course there is a kernel comment style.

Greetings
Bernd

eckes privat - http://www.eckes.org/
Project Freefire - http://www.freefire.org/

Uttered Bernd Eckenfels <[email protected]>, spake thus:

Therefore, kernel code is better than wrong comments?

Just trying to complete the syllogism ;-)

Then why haven't you done it already ? ;)

On a more serious note, some other people are already auditing the code on a regular basis, while you weren't paying attention ...

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Alright, it's a big undertaking ;)

I'm suggesting things to make code auditing simpler, more accurate, more precise. "Quality-Assurance audited code still contains on average 5 bugs per kloc" is a really nasty thought.

http://lkml.org/lkml/2004/8/9/369 was the major explaination. It's big and clunky to have before each function; but at least it's not ugly, and it's potentially helpful. Maybe a few of the like in the smallest driver possible to see how it feels? (/dev/mem?)

All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

On Mon, Aug 09, 2004 at 07:09:55PM -0400, John Richard Moser wrote:
...

...

There's just more to it than this.

Even in the almost "self explanatory" example you gave, even with your suggested style of commenting, there are still problems:

Your comments do not describe who's responsible for allocating/freeing which memory areas the various pointers point at.

Your get_food() function will cause a write at address 0 if malloc() fails.

So, you have provided some good examples that no particular commenting style is going to solve the common problems that all larger C software projects face to some extent (memory management and error handling).

...

Agreed :)

That's where I disagree.

They do provide an illusion of knowledge though (for example, you did not mention the built-in segfault mechanism, that was a hidden feature).

Comments are good. Frequent comments are very good - if they are correct and actually helpful.

I view it this way; if code is not commented, the only explanation is that the author didn't feel it was worth commenting. Code that is not worth even a comment, should be removed from whatever project it is in,
to be replaced by something actually worth commenting. (no, I'm not
bashing any particular part of the Linux kernel or anything like that - this is my personal view for projects that I'm involved in).

However; comments are NOT a substitute for all the other aspects required for good and reliable code.

Comments are one little part of the larger puzzle. Ignoring their importance is inexcusable - but they are not the magic silver bullet all by themselves either.

My 0.02 Euro
(as someone working on another large project that actually needs
to run reliably)

 / jakob

Then my comment above is bad. Should add that it frees the old block.

My code is bad probably. I should return if malloc() fails.

Memory managment is annoying. I'm working on a reference counting scheme on the side; but that's a fair bit of overhead. I've never been able to argue that reference counting is less overhead than manual mm; but I've also never been able to argue that trying to guess if you can free memory based on your program's internal state is less overhead than reference counting.

There's places where this is inappropriate, and places where it's appropriate. Inside the kernel, though, I can't imagine where it'd be appropriate. . . . yeh this is a bad idea, isn't it? :p

The function isn't made to segfault; segfaulting is what happens when you screw up your code. :)

I guess it should describe INPUT, OUTPUT, PROCESS, STATE CHANGE, and ERRORS :/

Readable. Don't guess what the code does.

Of course not. The goal I was aiming for was to create an extremely structured documentation scheme in the hopes that it would provide a great deal of ease in understanding what a function does. "if you don't understand what it does, don't fuck with my code"

All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

You do not need to describe behaviour if the pre-condition is not valid. This is common asumption in "design by contract". However, this is not good robust programming, to not handle those pre-condition violations.

What else is the author of the comment doing? You cant describe all (important) aspects of a piece of code in a language that is less complex than the code itself (locking, concurrency, mm, ressouce consumption, ...). In fact you are very likely introducing errors. Thats why comments are only needed for navigating you and giving you the overall picture. They are also good to explain unusual statements (especially in optimized hot path).

Well, actually it is good to describe a function at the high level, but dont go further than that.

Greetings
Bernd

eckes privat - http://www.eckes.org/
Project Freefire - http://www.freefire.org/

I believe that you should not believe such things. They are just statistics and nothing more.

If you have a 1000 lines project and:

a) Remove all empty lines means that you remove bugs?
b) Split it to 5 libraries and 5 utilities (10 projects) means that you'll have less bugs?
c) ....

I don't take generalizations like this seriously and I believe that noone should do. It may be true that 10.000 lines of code contain 50 bugs as an average of all the code that has be written so far but it doesn't mean that:

a) 50 bugs require 10.000 lines
b) 50 bugs will always exist on 10.000 lines
c) All the projects out there have the same number of bugs/line

<<V13>>

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

V13 wrote:

| On Monday 09 August 2004 23:07, John Richard Moser wrote:
|
|>What I found interesting was that it described bugs as
|>pseudo-quantitative based on the KLOC (thousands of lines of code) for a
|>code body.  The basic theory boils down to 5-50 bugs per 1000 LOC,
|>approaching 5 for QA audited code.  Thus, 10000 LOC executable, 50 bugs.
|
|
| I believe that you should not believe such things. They are just

statistics
| and nothing more.
|

Statistics are as a whole, not as a part. This makes statistics a powerful art.

| If you have a 1000 lines project and:
|
| a) Remove all empty lines means that you remove bugs?
| b) Split it to 5 libraries and 5 utilities (10 projects) means that
you'll
| have less bugs?
| c) ....
|
| I don't take generalizations like this seriously and I believe that noone
| should do. It may be true that 10.000 lines of code contain 50 bugs as an
| average of all the code that has be written so far but it doesn't mean
that:
|
| a) 50 bugs require 10.000 lines
| b) 50 bugs will always exist on 10.000 lines
| c) All the projects out there have the same number of bugs/line
|

No, but it means in a sample of one hundred and twenty eight billion lines, there will be approximately fifty bugs per 10000 lines of code.

|
|>--John
|
| <<V13>>
|

- --
All content of all messages exchanged herein are left in the Public Domain, unless otherwise explicitly stated.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFBGVvBhDd4aOud5P8RAlwKAJ0Ut0XoyibvkQ9THUT1YvcoufebdwCeJmNC PqZqaKCTrdpA2DyZydcT9Cw=
=pAJZ
-----END PGP SIGNATURE-----

No because LOC is defined on a more abstract level. It is not about "wc -l", but there are various methods, and all basically count the number of statement. Accounting brnaches and nifty shortcuts more than normal statements. I suggest you read about the "Personal Software Process", it very well describes the numbers you can get, and the questions they answer (and especially which numbers are not compareable).

You will most likely add additional lines, and of course having 5 projects with 500 lines has not less bugs than 1 project with 2500 loc. BTW: of course it might make the programs more manageable since it explictely introduces more boundaries and interfaces. Read some statements from DJB (Sorry!) on that.

Hmm.. i used to learn the meaning of average at the university, and nobody claims that those statements are true! Average statstics is good for benchmarking, and you would be surprised how fairly stable those bug counts are.

Greetings
Bernd

eckes privat - http://www.eckes.org/
Project Freefire - http://www.freefire.org/