SPONSORS:






User Tag List

Thanks Thanks:  0
Likes Likes:  0
Dislikes Dislikes:  0
Results 1 to 4 of 4
  1. #1
    Junior Member
    Join Date
    Dec 2000
    Location
    Montréal, Québec, Canada
    Posts
    27
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Total Downloaded
    0

    Proofs Of Correctness: Is it dead?

    Hi everyone,

    I'm currently evaluating the idea of implementing proofs of correctness for critical algos. I've made a search on this forum on this matter and only found one of my reply.

    Anyone with expertise on this subject?
    If so, I would like to hear from you!

    I've heard a lot, but mostly from the academic point of view.

    Any help will be appreciated!

    Kemdak


    ------------------

  2. #2
    Senior Member
    Join Date
    May 2001
    Location
    München, Germany
    Posts
    171
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Total Downloaded
    0

    Re: Proofs Of Correctness: Is it dead?

    It depends on the industry you are in and the actual importance of the algorithm.

    Proofs of correctness should probably be done if a failure of the alrogithm may result in:
    -> Death or injury
    -> Significant capital destruction
    -> Disruption of a social system
    That is from the ethical point of view.

    From the business point of view:
    -> Complete failure of the application
    -> Disablement of customer's process

    You need to define some sort of criteria as to when to do algorithm proofs, especially if you need to do proofs of code (which is a little more difficult).

    The best is to outline your requirements of success (using some of the above points as guidlines). Does confidence in this component need to be 99%, 99.9%, 99.99%, 99.999%, or even higher?

    Certain industries, like aviation, have fault tolerance meaured in the millions of hours. That is, certain systems are mandated by regulatory agencies to have a Mean-time-before-failure that exceeds the lifespan of several generations of individuals.

    If you are writing software for Windows though, there is no point in achieving extremely high quality, since windows itself cannot ensure your application will even be allowed to ensure such fault tolerance (that is, your quality cannot exceed that of the system it operates on by more than a fractional amount).



    ------------------
    edA-qa mort-ora-y
    QA Manager
    --
    edA-qa@disemia.com
    TestPlan - Superior Web Application Automation & Testing

  3. #3
    Junior Member
    Join Date
    Dec 2000
    Location
    Montréal, Québec, Canada
    Posts
    27
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Total Downloaded
    0

    Re: Proofs Of Correctness: Is it dead?

    Thanks for your input Mortoray,

    The only thing that let me perplex is this statement:

    <BLOCKQUOTE><font size="1" face="Verdana, Arial, Helvetica">quote:</font><HR>Originally posted by mortoray:

    If you are writing software for Windows though, there is no point in achieving extremely high quality, since windows itself cannot ensure your application will even be allowed to ensure such fault tolerance (that is, your quality cannot exceed that of the system it operates on by more than a fractional amount).

    <HR></BLOCKQUOTE>

    It may apply to realtime systems that need little or no crash, but not all critical apps are realtime. If integrity of data is of prime concern and MTTF of the system isn't (here we're talking of failures that doesn't have an impact on data) then I think that it is reasonable to assume that NT/2000 apps can be pretty reliable under certain constraints.

    In any case, I understand that we're at the mercy of the OS that we use and that a complete proof would go to an nearly infinite number of levels of abstraction, but my objectives are more to give a good idea that critical algorithms do what they're supposed to do. And use testing techniques for the implementation.

    Thanks for your help,

    Kemdak

    ------------------

  4. #4
    Senior Member
    Join Date
    May 2001
    Location
    München, Germany
    Posts
    171
    Post Thanks / Like
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Total Downloaded
    0

    Re: Proofs Of Correctness: Is it dead?

    I agree that potentially I may have partially confused critical algorithms with real-time systems.

    Though, my point about Windows still stands (although it does apply to all operating systems, not just windows). If your algorithm makes use of memory, or some kind of system resource (maybe a timer, or DMA channel), the guarantees of the system become relevant.

    Under Win2000 you can be reasonably well assured that your memory is protected if you keep it within a single process and do not use threads. This may not be the case on Win98.

    And if you are writing device drivers, you have this extra amount of concern as your memory may not be protected at all.

    So if you have a critical algorithm on these systems, and the above concerns are valid, or there are other OS imposed concerns, proving the correctness of the algorithm may include proving validity of its fault tolerance.

    But I guess I should have a more significant point to make than this. What I meant about the fractional amount is that it is hard to overcome limitations of the system.

    Let's assume you make the assumption that your algorithm makes the assumption of 100% memory correctness and the operating system, or hardware, is only guaranteeing 99% correctness. Your confidence level in the algorithm can only reach 99%. So you may wish to limit your proof effort to the point where you feel that statistically the memory will fail before the algorithm does.

    What I fear however is that many teams take the attitude that, "Windows crashes all the time, so why should I put much effort into my application". Which simply means Windows fails even more often...


    ------------------
    edA-qa mort-ora-y
    QA Manager
    --
    edA-qa@disemia.com
    TestPlan - Superior Web Application Automation & Testing

 

 

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Search Engine Optimisation provided by DragonByte SEO v2.0.40 (Pro) - vBulletin Mods & Addons Copyright © 2017 DragonByte Technologies Ltd.
Resources saved on this page: MySQL 11.54%
vBulletin Optimisation provided by vB Optimise v2.7.1 (Pro) - vBulletin Mods & Addons Copyright © 2017 DragonByte Technologies Ltd.
User Alert System provided by Advanced User Tagging v3.3.0 (Pro) - vBulletin Mods & Addons Copyright © 2017 DragonByte Technologies Ltd.
vBNominate (Lite) - vBulletin Mods & Addons Copyright © 2017 DragonByte Technologies Ltd.
Feedback Buttons provided by Advanced Post Thanks / Like (Pro) - vBulletin Mods & Addons Copyright © 2017 DragonByte Technologies Ltd.
Username Changing provided by Username Change (Free) - vBulletin Mods & Addons Copyright © 2017 DragonByte Technologies Ltd.
BetaSoft Inc.
Digital Point modules: Sphinx-based search
All times are GMT -8. The time now is 09:03 PM.

Copyright BetaSoft Inc.