[RFC] Bug zapper? :)

[RFC] Bug zapper? :)

[John Richard Moser]

(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.

Re: [RFC] Bug zapper? :)

[John Richard Moser]

Denis Vlasenko wrote:
> On Monday 09 August 2004 23:07, John Richard Moser wrote:
> 

[...]

> 
> 
> The flaw is that you think that kernel folks don't review their code.
> However, if you see some bad code, by all means - send a patch.
> 

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.

> Asking others to do large amount of work is not very popular on this list.
> Do something yourself first.

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.
> --
> vda
> 
> 

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

Re: [RFC] Bug zapper? :)

[Bernd Eckenfels]

In article <41180443.9030900@comcast.net> you wrote:
> The large amount of extra commentary is worth it, IMHO.

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/

Re: [RFC] Bug zapper? :)

[Tommy Reynolds]

Uttered Bernd Eckenfels <ecki-news2004-05@lina.inka.de>, spake thus:

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

Therefore, kernel code is better than wrong comments?

Just trying to complete the syllogism ;-)

Re: [RFC] Bug zapper? :)

[Rik van Riel]

On Mon, 9 Aug 2004, John Richard Moser wrote:

> What I'm suggesting isn't much though, is it really? 

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

Re: [RFC] Bug zapper? :)

[John Richard Moser]

Rik van Riel wrote:
> On Mon, 9 Aug 2004, John Richard Moser wrote:
> 
> 
>>What I'm suggesting isn't much though, is it really? 
> 
> 
> Then why haven't you done it already ? ;)
> 

Alright, it's a big undertaking ;)

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

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.

Re: [RFC] Bug zapper? :)

[Jakob Oestergaard]

On Mon, Aug 09, 2004 at 07:09:55PM -0400, John Richard Moser wrote:
...
> 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.
> */
...

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).

...
> These comment blocks are *MUCH* more verbose.

Agreed  :)

> They describe the process 
> loosely, but do give enough information to allow understanding without 
> questions.

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).

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

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

Re: [RFC] Bug zapper? :)

[John Richard Moser]

Jakob Oestergaard wrote:
> On Mon, Aug 09, 2004 at 07:09:55PM -0400, John Richard Moser wrote:
> ...
> 
>>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.
>>*/
> 
> ...
> 
> 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.
> 

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

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

My code is bad probably.  I should return 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).
> 

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


> ...
> 
>>These comment blocks are *MUCH* more verbose.
> 
> 
> Agreed  :)
> 
> 
>>They describe the process 
>>loosely, but do give enough information to allow understanding without 
>>questions.
> 
> 
> 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).
> 

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 :/

> 
>>The large amount of extra commentary is worth it, IMHO.
> 
> 
> 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.
> 

Readable.  Don't guess what the code does.

> 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.
> 

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"

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

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

Re: [RFC] Bug zapper? :)

[Nick Warne]

"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."

I really disagree with stuff like this.

OK, I am not a contributer to kernel code - far from it - nor really any sort 
of coder at all except I can read it all and try to understand.

But why does 'quality assurance' == less bugs (or whatever you try it on - and 
take we know who for an e.g.)?

It doesn't.  All it does is give a 'false' assurance to something that when 
tested and looked at didn't find what it was searching for to look at and 
find - and of course, who/whatever does the assessment needs to be 'QA'ed' 
first to make sure that is correct - so what/who does that?

If the code is 'Assured clean' then should everybody accept it and carry on to 
the next bit?

Quality assurance may work in the manufacturing industry (sort of), but in 
abstract fluent work...

Many eyes is the only way, reading and re-reading.

Nick


-- 
"When you're chewing on life's gristle,
Don't grumble, Give a whistle..."

Re: [RFC] Bug zapper? :)

[V13]

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. 

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

> --John
<<V13>>

Re: [RFC] Bug zapper? :)

[Bernd Eckenfels]

In article <4118E78F.8070301@comcast.net> you wrote:
> I guess it should describe INPUT, OUTPUT, PROCESS, STATE CHANGE, and 
> ERRORS :/

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.

> Readable.  Don't guess what the code does.

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).

> 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"

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/

Re: [RFC] Bug zapper? :)

[John Richard Moser]

-----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-----

Re: [RFC] Bug zapper? :)

[Bernd Eckenfels]

In article <200408110030.37601.v13@priest.com> you wrote:
> If you have a 1000 lines project and:
> 
> a) Remove all empty lines means that you remove bugs?

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).

> b) Split it to 5 libraries and 5 utilities (10 projects) means that you'll 
> have less bugs? 

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.


> 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

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/