Формални методи

В компютърните науки и софтуерното инженерствоформалните методи(англ. formal methods) е група от техники, базирани на математическия апарат за спецификация, разработване и проверка на софтуер и хардуер [1] . Използването на формални методи за проектиране на софтуер и хардуер се дължи на очакването, че както в други инженерни области, използването на математически анализ може значително да повиши надеждността на системите [2] . В същото време формалните методи са доста сложни, изискват специално обучение, инвестиции на време и ресурси и често се основават на предположения, които не винаги са постижими в реални условия. Това води до факта, че формалните методи се използват най-често при проектирането на високопрецизни системи, където важността на безопасността оправдава всякакви средства.

Съдържание

Има три нива на приложение на формалните методи:

Ниво нула Разработва се официална спецификация, след което се пише код, като се разглежда. В този случай разликата между формалната и неформалната част остава недоказана, но решението може да бъде рентабилно. Първо ниво Програмният код се извлича автоматично от формалната спецификация, използват се механизми за проверка и се доказват най-критичните свойства на системата. Този път често се избира за системи с висока точност. Ниво 2 Автоматизирани доказатели на теореми се използват за извличане на напълно формализирани доказателства, които могат да бъдат проверени автоматично. Подходът изисква много инвестиции и изследвания, но се отплаща в най-критичните части на сложни системи, където грешките са недопустими (например при проектирането на интегрални схеми).

Подходиформалните методи също могат да бъдат класифицирани по начин, подобен на формалната семантика на езиците за програмиране:

Денотационна семантика Значението на една система се изразява чрез частично подредени множества, а методите разчитат на добре развита теория около тях. Ограничението на метода е, че не всяка система може да бъде интуитивно или естествено разглеждана като функция. Оперативна семантика (англ. operational semantics) Стойността на системата се обозначава чрез последователност от действия в рамките на по-прост изчислителен модел (например ламбда смятане или мрежи на Петри). Методите са известни със своята простота, ако не се подчертава фактът, че разчитат на семантиката на „по-проста“ система, която също трябва да бъде дефинирана чрез нещо. Аксиоматична семантика (англ. axiomatic semantics) Значението на системата се определя от гледна точка на предпоставки и постусловия, което ви позволява да свържете теорията с класическата логика, но не дава представа какво точно се случва вътре в системата (как постусловията се постигат въз основа на предпоставки).

В допълнение, често драматично положителни резултати могат да бъдат постигнати чрез жертване на глобалната приложимост и свръхформализация - такива случаи се наричат "олекотени" (олекотени) формални методи. Те могат да бъдат разделени на два вида: с подобрена и с отслабена автоматизация. Пример за подобрена автоматизация е анализаторът на спецификациите на Alloy Analyzer, който, за да намали проблема с търсенето на модел до разрешим, стеснява областта на търсене (в резултат на това Alloy работи напълно автоматизирано, за разлика от интерактивните проувъри, но има шанс да не намери някои проблеми). Пример за отслабена е конвергенцията на граматиките, при която се заобикаля неразрешимостта на проблема за еквивалентността на два формални езикафактът, че трансформациите се извършват от самия човек и вече се правят изводи от свойствата на използваните от него оператори.

Формалните методи се прилагат на различни етапи от разработката на софтуера:

Спецификация С помощта на формални методи е възможно да се опише бъдещата система с всякакво ниво на детайлност. Такова формално описание може да се използва пряко или непряко за предимство на по-късни етапи. В същото време работата по доказването на редица необходими функционални свойства може да започне веднага и да върви успоредно с писането или генерирането на код. Съществуват редица езици и изчисления за формални спецификации, но никой не може да претендира, че е толкова универсален, колкото формата на Backus-Naur за спецификация на синтаксиса. Разработване Ако формалната спецификация използва оперативна семантика, наблюдаваното поведение на определена система може да се сравни с очакваното поведение, тъй като такава семантика може да е осъществима и може дори да се използва за автоматично генериране на код. Ако се използва аксиоматична семантика, тогава предусловията и постусловията могат да се съпоставят директно с изрази в изпълним код. Проверка След като бъде изготвена официална спецификация, тя може да се използва за доказване на изискваните свойства. Проверката може да бъде дедуктивна и моделна: дедуктивната използва автоматично доказателство на теореми или специфични алгебри, а моделната базира своите заключения не на самата система, а на модела, изграден върху нея [4] . В същото време абсолютно не е необходимо моделът да се изгражда ръчно, ако са приложими техники като програмен раздел (английски).

Ръчните доказателства изискват значителна инвестиция на ресурси и не осигуряват никаква полза освен потвърждение на коректността. В резултат на това се използват формални методиили в онези области, където доказателствата могат да бъдат получени автоматично чрез софтуер, или в тези, където цената на грешката е твърде висока (например при създаване на космически кораб или магнитно резонансно изображение).