Certified C compilers for safety-critical embedded systems - Page 4

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Re: Certified C compilers for safety-critical embedded systems

Quoted text here. Click to load it



While most C compilers and lint won't find this, there are static analysis
tools that can. Granted the
tools may be able to do a better job on Ada code because there is more
information to work with but
simple cases like you presented here (even if the loop was "far away:" from
foo) can be detected
by tools like Programming Research QA C (No Ada Available) and Polyspace
(Ada available)..

Perhaps even by the LDRA static analysis tools (Ada available) though I have
less to go on for this tool.



Re: Certified C compilers for safety-critical embedded systems

Quoted text here. Click to load it

Of course, static analysis for any language has its limitations.
For example, what tool exists for C that will reliably identify
the following problem:

int foo[10];

int total(int *a)
{
   int i;
   int sum = 0;
   for(i = 0; i < 100; ++i)
   {
      sum += a[i];
   }
   return sum;
}

Of course, the common C idiom is to pass a limit value along
with the array reference.

int total(int *a, int limit)
{
   int i;
   int sum = 0;
   for(i = 0; i < limit; +=i)
   {
      sum += a[i];
   }
   return sum;
}

The problem is that there is no explicit relationship between
the value passed to the formal parameter "limit" and the number
of elements in the array. It is up to the programmer to ensure
correctness in this detail.

Ada, on the other hand, provides a completely safe syntax to
deal with such problems.

type my_index is range 0..9;

type my_array is array(my_index range <>) of integer;

function total(a : my_array) return integer is
   sum : integer := 0;
begin
   for i in a'range loop
      sum := sum + a(i);
   end loop;
   return sum;
end total;

The Ada run-time will produce a correct iteration through
the array passed to total every time. The compiler will detect
any attempt to pass an parameter that is not of the type my_array.

This is clearly not a case that can be fully handled using static
analysis. Nevertheless, it must be handled correctly for all valid
cases. In Ada it can be proven that the iterations will always be
correct. In C there is no such proof possible. You must rely upon
the skills and attention of the programmer.

When reliability engineers encounter a system relying upon human
actions the commonly accepted error rate, assuming properly trained
humans, is 1 in 1000. Such an error rate is unacceptably low for
most safety critical systems. An error rate of 1 in 1000 is a
reliability rate of 0.999. Safety critical systems commonly
require reliability rates on the order of 0.999999. This is
three orders of magnitude higher than can be achieved through
reliance on human correctness.

Jim Rogers

Re: Certified C compilers for safety-critical embedded systems
Quoted text here. Click to load it
... snip ...
Quoted text here. Click to load it

And even then, 1000 such 6 nines reliable systems together can be
expected to have a combined reliability of 0.999.  Now consider
the count of individual transistors in a moderately complex
processor.

There are two basic methods of improving the end product
reliability:  Improve the component reliability, and reduce the
number of components.  This argues heavily against using a Pentium
when a PIC will do.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: Certified C compilers for safety-critical embedded systems

Quoted text here. Click to load it

Interesting argument but a potentialy flawed example.  First one pentium and
one pic are each one component so no reduction in components. More
importantly, though a Pentium may have more transistors in it than a PIC
and hence might be seen as more complex, it is not necessarily less
reliable.  Indeed given the relatives quantities manufactured the pentium
might well be much more reliable than the PIC.

Ian


Re: Certified C compilers for safety-critical embedded systems
Quoted text here. Click to load it

I disagree.  The basic components may have different reliability
figures, but both chips are made up of various implantations,
etchings, and aluminum layers, which create a whole aggregate of
components of varying reliability.  In both cases the user never
gets to see the fundamentally flawed components, because of
manufacturers final test.  I daresay the percentage yield for PICs
is considerably higher than that for Pentia, and this is reflected
in the price.

You also need to consider the MTBF of components.

Contrast the up times of early vacuum tube computers, later more
complex transistor/diode machines, still later SSI (7400 gates
etc) generations, and today almost everything is lumped onto one
or two chips.  The component count keeps going up, but the dodgy
interconnects and packaging goes down.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: Certified C compilers for safety-critical embedded systems

Quoted text here. Click to load it

Except yield and component reliability are not (necessarily) related.
Furthermore, the greater volumes of pentiums manufactured means that SPC
will have identified process and product weaknesses and improved both yield
and reliability.

Quoted text here. Click to load it

Don't disagree with that at all.

ian



Component Reliability (was Re: Certified C compilers for safety-critical embedded systems)
Quoted text here. Click to load it

I seriously doubt that Pentium volume exceeds PIC volume.  A lot
of this discussion depends on how you describe a component.  A car
is a component of a fleet, while a wheel is a component of a car,
etc.  You can never measure reliability, only calculate
probabilities.  In some cases you derive these from components, in
others you use experimental sampling, in still others you rely on
educated guesswork.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: Component Reliability (was Re: Certified C compilers for safety-critical embedded systems)
Quoted text here. Click to load it

It doesn't AFAIK  the last sets of figures I saw (broadly similar from
more than one silicon vendor) the x86 class only make up around 5% of
the MUC/MCP's produced. Around 25% are 8051 types.


/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England    /\/\/\/\/\
/\/\/ snipped-for-privacy@phaedsys.org       www.phaedsys.org \/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

Re: Component Reliability (was Re: Certified C compilers for safety-critical embedded systems)


 >> I seriously doubt that Pentium volume exceeds PIC volume.
 >
 >
 >
 > It doesn't AFAIK  the last sets of figures I saw (broadly similar from
 > more than one silicon vendor) the x86 class only make up around 5% of
 > the MUC/MCP's produced. Around 25% are 8051 types.


Do you have a reference? Many years ago I read an article about
microcontrollers being responsible by 95% of the market despite all the
hype created around either Intel or AMD release of a new top
microprocessor. I think the figure was related to market share ($$$),
not units shipped. The former makes more sense to me as nowadays there
are microcontrollers (from 4 to 32 bitters) in nearly every electricity
powered stuff you may think of. If I am right, then the figures for
units shipped are even more impressive due to cost per unit.

Regards.

Elder.


Re: Component Reliability (was Re: Certified C compilers for safety-critical embedded systems)
Quoted text here. Click to load it



/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England    /\/\/\/\/\
/\/\/ snipped-for-privacy@phaedsys.org       www.phaedsys.org \/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

Re: Component Reliability (was Re: Certified C compilers for safety-critical embedded systems)
Quoted text here. Click to load it
???????????????????????????????????


Re: Certified C compilers for safety-critical embedded systems

snip
Quoted text here. Click to load it

I know nothing about ada so this is a genuine query rather than a ctiticism.
The above example is fine as long as literals are used - even a C compiler
could be devised to make this check - but what happens when the array index
is computed?

Ian


Re: Certified C compilers for safety-critical embedded systems

Quoted text here. Click to load it

You mean as in

  type my_index is range 0 .. some_variable;

-- yes, Ada compilers will perform the check.

Actually the code wasn't actually compiled by whoever posted it, a
crime on c.l.a: you either have to say

  for Num in 0 .. 99 loop
     Foo (My_Index (Num)) := Num;
  end loop;

(which GNAT doesn't see as a problem until execution time) or

   for Num in My_Index range 0 .. 99 loop
      Foo (Num) := Integer (Num);
   end loop;

to which GNAT says

constraints.adb:10:35: warning: static value out of range of type "My_Index"
defined at line 3
constraints.adb:10:35: warning: "Constraint_Error" will be raised at run time

(this is the "99").



Re: Certified C compilers for safety-critical embedded systems

Quoted text here. Click to load it

That was not what I had in mind and seems to me to be rather dodgy code.  i
was thinking more of the return value of some function being used as an
index to the array.

Ian


Re: Certified C compilers for safety-critical embedded systems
Quoted text here. Click to load it

Ada performs array bounds checking (logically) on every array reference, and
raises an exception if the array index is out of range, unless the programmer
disables it.  Every Ada toolset I have seen defaults to enabling array bounds
checking.  I am not certain but I *THINK* ANSI/MIL-STD-1815A (1983) requires the
toolset to work that way.

For something like this,

  for num in a'range loop
    a(num) = num;
  end loop;

the compiler can determine that num cannot go out of range, and suppress the
check.

For something like

   a(some_function(x,y,z)) = treasure; -- as opposed to trash

the compiler probably can't make that determination, and must compile in a test.



Re: Certified C compilers for safety-critical embedded systems
On Sat, 27 Dec 2003 17:08:43 +0000, Ian Bell

Quoted text here. Click to load it

Ian,

Depends on the relationship of the subtype of the function result to that
of the index type of the array.

If they're of the same subtype, or of subtypes derived from the same type
("compatible"), and have the same range, the indexing operation will work
because an out of range value would have raised an exception before the
function result returned.

If the subtypes are derived from the same type, but have different ranges,
a runtime check is performed to make sure the function result is within
the stated index range.

Finally, if they're incompatible subtypes (not derived from the same
ancestor type), you'll get a compile time error, unless you explicitly
convert the function result to a compatible subtype of the index type
(then the runtime check will be used as in the second case).

The checks can be explictly suppressed.

Re: Certified C compilers for safety-critical embedded systems

Quoted text here. Click to load it

Ah, so there are run time checks too.  I had not realised this.  What
happens when the check fails and what is the code overhead introduced by
the check?

Ian


Re: Certified C compilers for safety-critical embedded systems
Quoted text here. Click to load it
... snip ...
Quoted text here. Click to load it

You may well have control of 'what happens' via exception throwing
and trapping.  The overhead is likely to be well under 5% IIRC, as
shown by a study in Pascal 30 or more years ago.  The point is
that with close subtyping the compiler can derive those
expressions that require checks, and suppress most pointless
checks with ease.

For example, MAX(a + b) = MAX(a) + MAX(b).  If this is suitable,
it need not be checked.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: Certified C compilers for safety-critical embedded systems
:> You mean as in
:>
:>   type my_index is range 0 .. some_variable;
:>
:> -- yes, Ada compilers will perform the check.
:>
:
: That was not what I had in mind and seems to me to be rather dodgy code.  i
: was thinking more of the return value of some function being used as an
: index to the array.

That should depend on what the compiler can find out about the
function.  For example, if there is "type Index is range 0..359;",
then if a function is specified to return values of a constrained
subtype of Index ranging from 0..179, and a buffer has been allocated for
some Index subtype's values ranging from 180..359, the compiler will
warn if you use the function's values as indices to the array,
_although_ in C terms the array index values and the function return
values are indistinguishable (both unsigned shorts for example).
I.e.
   type Index is range 0..359;
   subtype First_Half is Index range 0..179;
   subtype Second_Half is Index range 180..359;

   buffer: array(First_Half) of Some_Decimal_Type;

   function some_val return Second_Half;
   --  Second_Half values at random

...

    27.    if buffer(some_val) > 10.0 then
                     |
        >>> warning: value not in range of type "First_Half" defined at line 6
        >>> warning: "Constraint_Error" will be raised at run time


Re: Certified C compilers for safety-critical embedded systems

Quoted text here. Click to load it

So are you basically saying that Ada requires the function return type to be
bounded and can simply check this against the array bound?

Ian


Site Timeline