Ograniczanie wyników
Czasopisma help
Autorzy help
Lata help
Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 27

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  formal verification
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
EN
Cross modeling in embedded systems development is proposed in the paper. The main idea consists in a translation of SysML artifacts into the related Coloured Petri Net (CPN) models, which may be verified directly or using other tools, e.g. Temporal Logic Provers. The paper is an extension of [20] mainly by insertion of sequence diagrams (SysML) and presentation of their mapping into CPN models. The additional part describes communication features and completes the cross modeling approach.
EN
Parity games are infinite-duration two-player turn-based games that provide powerful formal-method techniques for the automatic synthesis and verification of distributed and reactive systems. This kind of game emerges as a natural evaluation technique for the solution of the μ- calculus model-checking problem and is closely related to alternating ω-automata. Due to these strict connections, parity games are a well-established environment to describe liveness properties such as “every request that occurs infinitely often is eventually responded”. Unfortunately, the classical form of such a condition suffers from the strong drawback that there is no bound on the effective time that separates a request from its response, i.e., responses are not promptly provided. Recently, to overcome this limitation, several variants of parity game have been proposed, in which quantitative requirements are added to the classic qualitative ones. In this paper, we make a general study of the concept of promptness in parity games that allows to put under a unique theoretical framework several of the cited variants along with new ones. Also, we describe simple polynomial reductions from all these conditions to either Büchi or parity games, which simplify all previous known procedures. In particular, they allow to lower the complexity class of cost and bounded-cost parity games recently introduced. Indeed, we provide solution algorithms showing that determining the winner of these games is in UPTIME ∩ COUPTIME.
EN
The paper concerns the problem of Boolean satisfiability checking, which is recognized as one of the most important issues in the field of modern digital electronic system verification and design. The paper analyzes different strategies and scenarios of the proving process, and presents a modified and extended version of the author’s FUDASAT algorithm. The original FUDASAT methodology is an intuitive approach that employs a commonsense reasoning methodology. The main objective of the work is to investigate the SAT-solving process and try to formulate a set of rules controlling the reasoning process of the FUDASAT inference engine. In comparison with the author’s previous works, the paper introduces new mechanisms: hypergraph analysis, multiple variable assignments and search space pruning algorithms. The approach considers only 3-SAT class functions, although a generalization of the method is discussed as well. The presented approach has been tested on various benchmarks and compared with the original pure FUDASAT algorithm as well as with other algorithms known from the literature. Finally, the benefits of the proposed SAT solving technique are summarized.
EN
The work concerns formal verification of workflow-oriented software models using the deductive approach. The formal correctness of a model’s behaviour is considered. Manually building logical specifications, which are regarded as a set of temporal logic formulas, seems to be a significant obstacle for an inexperienced user when applying the deductive approach. A system, along with its architecture, for deduction-based verification of workflow-oriented models is proposed. The process inference is based on the semantic tableaux method, which has some advantages when compared with traditional deduction strategies. The algorithm for automatic generation of logical specifications is proposed. The generation procedure is based on predefined workflow patterns for BPMN, which is a standard and dominant notation for the modeling of business processes. The main idea behind the approach is to consider patterns, defined in terms of temporal logic, as a kind of (logical) primitives which enable the transformation of models to temporal logic formulas constituting a logical specification. Automation of the generation process is crucial for bridging the gap between the intuitiveness of deductive reasoning and the difficulty of its practical application when logical specifications are built manually. This approach has gone some way towards supporting, hopefully enhancing, our understanding of deduction-based formal verification of workflow-oriented models.
PL
Schemat ideowy układu elektronicznego jest zbiorem wzajemnie ze sobą połączonych elementów elektronicznych tworzących pewną sieć. Sieć ta jest strukturą, która może być w automatyczny sposób odczytywana analizowana. Automatyczna weryfikacja formalna schematu ideowego ma na celu wykrycie nietrywialnych błędów popełnionych przez projektanta w trakcie opracowywania schematu ideowego. W ramach analizy sprawdzana jest poprawność struktury i zgodność wartości wybranych parametrów tworzonego schematu w odniesieniu do - zdefiniowanych wcześniej - typowych bloków funkcyjnych. W artykule przestawiono przykładową realizację automatycznej weryfikacji formalnej przeprowadzaną w celu dokonania analizy klucza tranzystorowego począwszy od definicji okładu klucza tranzystorowego, przez sposób dostępu do schematu, po automatyczną identyfikację bloków funkcyjnych.
EN
Schematic diagram can be interpreted as set of components connected with themselves together to build a network. The network is a structure, which topology that can be red and analyzed. Automatic formal verification aims to detect some non-trivial mistakes, made by electrical engineer, connected with structure of a schematic, building blocks and typical functional sub-circuits. The article presents approach to realize automatic formal detection tool starting from definition of schematic structure, though connectivity with schematic-capture tool, to sub-circuit identification algorithm.
6
EN
This work concerns issues related to automatic generation of logical specifications. Logical specifications can be extracted directly from developed software models. Received specification can be used in the process of a system formal verification using a deductive approach. The generated logical specification is just a set of temporal logie fonnulas as well as verified system properties are expressed in temporal logie. The extraction process is based on the idea of organizing the whole analyzed model as a set of certain design patterns of control flows. A method of automatic transformation of workflow design patterns to temporal logie formulas is proposed. These formulas constitute a logical specification and may be the first step towards a formal verification of system correctness using any method of the deduction-based reasoning. Applying the presented concepts enables bridging the gap between naturalness and intuitive of the deductive inference and the difficulty of its practical application in the case of software models.
PL
Praca dotyczy zagadnień związanych z automatyczną generacją i modelowaniem specyfikacji logicznej. Specyfikacja logiczna może być wygenerowana bezpośrednio z modeli oprogramowania. Tak uzyskana specyfikacja następnie może być wykorzystana w procesie formalnej weryfikacji przy wykorzystaniu podejścia dedukcyjnego. Wygenerowana specyfikacja reprezentowana jest przez zbiór formuł logiki temporalnej, również weryfikowane własności systemu mogą i powinny być wyrażone w logice temporalnej. Proces ekstrakcji opiera się na założeniu, aby cały analizowany model oprogramowania został zbudowany w oparciu o przyjęte, dowolne, ale najlepsze dla danej klasy zastosowań, wzorce projektowe. Została zaproponowana metoda automatycznej translacji wzorców projektowych (przepływów) do postaci formuł logiki temporalnej. Formuły te składają się na logiczną specyfikację i mogą stanowić pierwszy krok w kierunku formalnej weryfikacji poprawności systemów z wykorzystaniem dowolnej metody wnioskowania dedukcyjnego. Zastosowanie przedstawionych koncepcji umożliwia połączenie naturalności i intuicyjności samego wnioskowania logicznego oraz praktycznego zastosowania tych metod w przypadku modeli oprogramowania.
PL
Artykuł przedstawia regułowy model logiczny rekonfigurowalnego sterownika logicznego opisanego za pomocą interpretowanej sieci Petriego, która jest formalną specyfikacją zachowania systemów dyskretnych. Model logiczny, jako abstrakcyjny opis, nadaje się zarówno do formalnej weryfikacji, jak i syntezy logicznej. W pracy są rozpatrywane różne warianty opisu reguł.
EN
The article presents rule-based logical model of reconfigurable logic controller, by means of Control Interpreted Petri Nets, which are formal specification of discrete systems behavior. Logical model, as an abstract description, is easy to formally verify and to synthesize. In the paper, various rules notations are discussed.
EN
The problem under discussion is to check whether a given system of incompletely specified Boolean functions is implemented by a logical description with functional indeterminacy that is represented by a system of connected blocks. Each of blocks is specified by a system of completely or incompletely specified Boolean functions. Simulation based and SAT based verification methods is considered. The first method simulates the structure specified by the second description on the domain of the first description. The second method formulates the verification problem as checking satisfiability of a conjunctive normal form. The results of computer investigation of the proposed methods are given.
PL
W artykule omówiono problem sprawdzania, czy dany układ częściowo określonych funkcji Boole'owskich jest realizowany przez specyfikację logiczną z indeterminizmem funkcjonalnym. Ta specyfikacja jest przedstawiona jako system połączonych bloków, z których każdy odpowiada układowi całkiem albo częściowo określonych funkcji Boole'owskich. Rozpatrzono metodę symulacyjną i metodę bazującą na analizie spełnialności funkcji. Pierwsza z tych metod symuluje strukturę, opisaną przez drugą specyfikację, w dziedzinie pierwszej specyfikacji. Druga metoda sprowadza problem weryfikacji do problemu spełnialności funkcji w postaci iloczynu sum. Przedstawiono wyniki komputerowych badań skuteczności zaproponowanych metod.
9
EN
The paper presents a novel approach to rule-based logic controller specification and its verification. The proposed abstract model is suited for formal verification (using model checking technique) as well as for logic synthesis (using hardware description language VHDL). Special focus is put on Interpreted Petri Nets with inhibitor and enabling arcs, their realization in rule-based model and, additionally, their interpretation in another logic controller specification technique - UML Activity Diagrams (version 2.x).
PL
Artykuł przedstawia nowatorskie podejście do regułowej specyfikacji sterownika logicznego, wraz z jej weryfikacją (walidacją). Proponowany abstrakcyjny model logiczny jest dogodny zarówno do formalnej weryfikacji modelowej, jak również do syntezy logicznej (język opisu sprzętu VHDL). Szczególną uwagę poświęcono łukom zakazującym i zezwalającym interpretowanych sieci Petriego. Po krótkim wprowadzeniu do omawianej tematyki (rozdział 2), przedstawiono przykład interpretowanej sieci Petriego z łukami zakazującymi i zezwalającymi (rys. 1). Podano sposób ich realizacji w abstrakcyjnym modelu logicznym (rozdział 3, schemat kompletnego proponowanego systemu na rys. 2 oraz przykład regułowego modelu sterownika logicznego na rys. 3). Zaproponowano interpretację łuków zakazujących i zezwalających sieci Petriego w innej postaci specyfikacji zachowania sterownika logicznego (rozdział 4) - diagramach aktywności języka UML (w wersji 2.x). Ze względu na bezstanowość diagramów aktywności, nie jest możliwe bezpośrednie odwzorowanie rozpatrywanych łuków. W artykule zaproponowano dwa rozwiązania - opierające się na wprowadzeniu dodatkowego sygnału (rys. 4a) oraz alternatywne - bazujące na etykietowaniu przepływów (rys. 4b). Przedstawiono sposób formalnej weryfikacji tak przygotowanej specyfikacji regułowej oraz jej syntezy logicznej (rozdział 5). Publikacja kończy się podsumowaniem oraz wnioskami (rozdział 6)
10
Content available Communication with Environment in Alvis Models
EN
Alvis is a modelling language defined for the design and a formal verification of embedded systems. An Alvis model is a system of agents that usually run concurrently, communicate one with another, compete for shared resources etc. Due to the fact that an embedded system usually collects inputs that come from its environment and provides outputs that go to the environment it is necessary to provide a mechanism to describe such a communication. In contrast to another formal languages used to model embedded systems it is not necessary, using Alvis, to design such an environment as a part of a model. The paper deals with the problem of modelling a communication with an embedded system environment with Alvis.
EN
The article presents a novel approach to formal verification of logic controller specification. Model checking technique is used to verify some behavioral properties. The approach proposes to use a rule-based logical model presented at RTL-level. Proposed logical model is suitable both for formal verification (model checking in the NuSMV tool) and for logical synthesis (using hardware description language VHDL). As the result, logic controller program (its implementation) will be valid according to its primary specification.
PL
Artykuł przedstawia nowatorskie podejście do formalnej weryfikacji specyfikacji sterownika logicznego. Zaproponowany został regułowy model logiczny, który jest dogodny zarówno do formalnej weryfikacji (weryfikacja modelowa w narzędziu NuSMV), jak również do syntezy logicznej (z użyciem języku opisu sprzętu VHDL). Program sterownika logicznego (jego implementacja) będzie zatem poprawny względem początkowej specyfikacji.
12
Content available Introduction to Alvis modelling language
EN
Alvis is a novel modelling language designed for embedded systems. It combines both high level programming language used to define agents behaviour with hierarchical graphical modelling language used to define interconnections between agents. The paper presents a survey of the most important features of the language.
PL
Alvis jest nowym językiem modelowania przeznaczonym do rozwijania systemów wbudowanych. Łączy w sobie cechy języków programowania wysokiego poziomu z hierarchicznym językiem modelowania połączeń między agentami. Podstawowym elementem języka Alvis są agenty, które mogą działać współbieżnie, komunikować się ze sobą, czy też współzawodniczyć o zasoby dzielone. Dynamika poszczególnych agentów jest opisywana w warstwie kodu używającej do tego celu języka programowania wysokiego poziomu (połączenie natywnych konstrukcji języka Alvis i języka funkcyjnego Haskell). W warstwie graficznej definiowane są połączenia między agentami wskazujące, które agenty się ze sobą komunikują i jaki jest kierunek tej komunikacji. Warstwa ta ma postać grafu hierarchicznego, co pozwala rozwijać systemu wbudowane metodą od ogółu do szczegółu lub odwrotnie. Formalną reprezentacjąmodelu w języku Alvis jest graf LTS (Labelled Transition System), który reprezentuje wszystkie osiągalne stany i przejścia między nimi. Graf ten jest stosowany do formalnej weryfikacji modelu. Artykuł zawiera przegląd najistotniejszych cech języka Alvis.
EN
SystemC is an IEEE standard system-level language used in hardware/software co-design and has been widely adopted in the industry. This paper describes a formal approach to verifying SystemC designs by providing a mapping to the process algebra mCRL2. Our mapping formalizes both the simulation semantics as well as exhaustive state-space exploration of SystemC designs. By exploiting the existing reduction techniques of mCRL2 and also its model-checking tools, we efficiently locate the race conditions in a system and resolve them. A tool is implemented to automatically perform the proposed mapping. This mapping and the implemented tool enabled us to exploit process-algebraic verification techniques to analyze a number of case-studies, including the formal analysis of a single-cycle and a pipelined MIPS processor specified in SystemC.
EN
This work presents a novel approach to SAT solving problem based on commonsense reasoning methodology. The methodology has been implemented and tested in PROLOG. Discussion of different modern approaches to the satisfiability that have been published recently is presented. A parallelism between the SAT solving problem and non-monotonic extensions verifying is given. The new algorithm of SAT solving based on fuzzy default reasoning (FDL) theory FUDASAT and cumulativity of CNF formulas is defined. Optimal backtracking search methodology is explained on examples. Some experiments on various benchmarks show the efficiency and advantages of the proposed methodology.
PL
Artykuł przedstawia nowe podejście do problemu badania spełnialności formuł logicznych oparte na metodzie wnioskowania zdroworozsądkowego. Zaproponowana metoda została zaimplementowana i przetestowana w środowisku języka PROLOG. Przeprowadzono szczegółową dyskusję dotyczącą istniejących nowoczesnych technik sprawdzania spełnialności formuł logicznych, które zostały opublikowane w ostatnich latach. Przedstawiono podobieństwa między problemem badania spełnialności formuł logicznych a weryfikacją rozszerzeń w logice niemonotonicznej. Sformułowano podstawowe założenia nowego algorytmu FUDASAT badania spełnialności formuł logicznych opartego na wnioskowaniu FDL oraz zdefiniowano problem kumulacyjności formuł w postaci normalnej CNF. Metoda optymalnego przeszukiwania podczas nawrotów została opisana na przykładach. Eksperymenty przeprowadzone na zestawach wzorcowych pokazują zalety proponowanej metody.
EN
The paper presents formal verification method of logic controller specification taking into account user-specified properties. Logic controller specification may be expressed as Petri net or UML 2.0 Activity Diagram. Activity Diagrams seem to be more user-friendly and easy-understanding that Petri nets. Specification in form of activity diagram may afterwards be transformed into Petri net, which may then be formally verified and used to automatically generate implementation (code). A new transformation method dedicated for event-driven systems is proposed. Verification process is executed automatically by the NuSMV model checker tool. Model description based on specification and properties list is being built. Model description derived from Petri net is presented in RTL-level and easy to synthesize as reconfigurable logic controller or PLC. Properties are defined using temporal logic. In model checking process, verification tool checks whether requirements are satisfied in attached system model. If this is not the case, appropriate counterexamples are generated.
PL
Praca prezentuje metodę formalnej weryfikacji specyfikacji sterownika logicznego uwzględniającą właściwości podane przez użytkownika. Specyfikacja sterownika logicznego może być przedstawiona m.in. w postaci sieci Petriego lub diagramu aktywności języka UML. Diagramy aktywności wydają się być bardziej przyjazne i zrozumiałe dla użytkownika niż sieci Petriego. Specyfikacja w postaci diagramu aktywności może zostać przekształcona do sieci Petriego, która następnie może być formalnie zweryfikowana i wykorzystana do automatycznej generacji implementacji (kodu). Węzły diagramu aktywności konsekwentnie interpretowane są jako tranzycje sieci Petriego, w odróżnieniu od klasycznego podejścia (w starszych wersjach UML) gdzie odwzorowywało się je jako miejsca sieci Petriego. Proces weryfikacji wykonywany jest automatycznie przez narzędzia weryfikacji modelowej. Tworzony jest opis modelu bazujący na specyfikacji oraz lista wymagań. Nowatorskim podejściem jest przedstawienie sieci Petriego na poziomie RTL w taki sposób, że łatwo jest przeprowadzić syntezę logiczną sieci w postaci współbieżnego rekonfigurowalnego sterownika logicznego lub sterownika PLC bez konieczności przekształcania modelu. Wymagania określone są przy użyciu logiki temporalnej. W procesie weryfikacji modelowej narzędzie weryfikujące NuSMV sprawdza, czy model systemu spełnia stawiane mu wymagania. Jeżeli tak nie jest, generowany jest odpowiedni kontrprzykład.
16
Content available Changing probabilistic beliefs in persuasion
EN
The aim of the paper is to extend our formal model of persuasion with an aspect of change of uncertainty interpreted probabilistically. The general goal of our research is to apply this model to design a logic and a software tool that allow for verification of persuasive multi-agent systems (MAS). To develop such a model, we analyze and then adopt the Probabilistic Dynamic Epistemic Logic introduced by B. Kooi. We show that the extensions proposed in this paper allow us to represent selected aspects of persuasion and apply the model in the resource re-allocation problem in multi-agent systems.
PL
Celem pracy jest rozszerzenie zaproponowanego przez nas formalnego modelu perswazji o aspekt zmiany niepewności przekonań agentów interpretowanych w teorii prawdopodobieństwa. Wzbogacony model jest podstawą do zdefiniowania logiki i zaprojektowania narzędzia, które umożliwia automatyczną weryfikację perswazyjnych systemów wieloagentowych. W celu realizacji tego zadania analizujemy i adaptujemy Probabilistyczną Dynamiczną Epistemiczną Logikę wprowadzoną przez B. Kooi. Zastosowanie zaproponowanego podejścia do analizowania wybranych aspektów perswazji omawiamy na przykładzie problemu alokacji zasobów w rozproszonych komputerowych systemach.
PL
W artykule przedstawiono wdrażaną metodę projektowania rekonfigurowalnych sterowników logicznych, ukierunkowaną na jakość behawioralnej specyfikacji, a tym samym niezawodność pracy. Zamierzone funkcjonowanie sterownika jest opisane z wykorzystaniem równocześnie dwóch dualnych języków graficznych: diagramu maszyny stanów UML oraz komplementarnej sieci Petriego. Synergia spowodowana dwoma wzajemnie się uzupełniającymi podejściami do behawioralnego opisu tego samego sterownika daje szansę na otrzymanie uwiarygodnionej specyfikacji już we wstępnej fazie projektowania.
EN
In the paper quality oriented approach to the design of digital embedded reconfigurable controllers is presented. The behaviour of a logic controller is described by means of dual related graphical languages: UML State machine diagram and Petri Net graph. The first one is well accepted among designers from the electronic industry, the second one among control engineers taking the advantage from similarities between Petri nets and Sequential Function Charts (SFC). The synergy of the view from two sides into the same project gives a chance to obtain validated specification at the design process beginning. It is shown in the second paragraph. Comparison of elementary models (Tab. 1) and design process with use of the dual specification (Fig. 1) are also presented. The third paragraph deals with mutual conversion of the elementary elements (Tab. 2) and shows their subsets in the form of class diagrams (Figs. 2 and 3). An example of the logic controller dual specification (Figs. 4 and 5) is given in the fourth paragraph. The practical use of dual specification is contingent upon implementation of tools for performing the conversion process in an automatic way.
PL
Artykuł dotyczy zagadnień weryfikacji formalnej złożonych systemów elektronicznych, tzw. SoC. W pracy zaproponowano nowe oryginalne podejście do planowania strategi weryfikacji opartej o wnioskowanie zdroworozsądkowe. Opisano formalną metodologię mechanizmu planowania bazującą na rozproszonej logice domniemań FDL (Fuzzy Default Logic). Zdefiniowano wieloetapową strategię weryfikacji w postaci narzędzia systemu weryfikacji związanej z określoną platformą sprzętowo-programową. Metodologia została zweryfikowana na prototypowej platformie SoC połączonej magistralą AMBA. Pokazano zalety proponowanego podejścia.
EN
The paper deals with problem of the formal verification of complex electronic embedded systems. A new commonsense strategy is proposed. The formal methodology of the inference engine modeling based on Fuzzy Default Logic is given. The multistage verification strategy as the platform dependent verification (PDV) toolset is defined. The methodology has been validated on examples on a prototype AMBA-based virtual SoC platform working with SystemVerilog verification procedures. The advantages of the presented methodology have been emphasized.
19
Content available remote Analysis and design of correct real-time safety-critical software
EN
High-energy physics experiments rely on large hardware installations. As these machines become more and more advanced, their maintenance becomes a complex task. The free-electron laser FLASH is not an exception. It is designed for delivering a high quality laser beam to scientific experiments round the clock. Each machine standstill costs extra money. Therefore, the maximization of its uptime plays an important role. Automation software is a means for improving machine availability. One expects to improve the machine uptime by automating routine tasks performed by the operators and by providing auto-recovery supervision software. The efforts presented in this contribution concern the elaboration of a general framework for the design and development of safe and predictable automation software. Devised tools and design methods are evaluated during the implementation of the automation software for a single RF-power station of the FLASH.
PL
Eksperymenty fizyki wysokich energii są możliwe dzięki zastosowaniu skomplikowanych instalacji eksperymentalnych. Z roku na rok urządzenia te stają się coraz bardziej skomplikowane a ich obsługa oraz serwisowanie staje się coraz bardziej złożona. Laser na elektronach swobodnych FLASH nie jest wyjątkiem. Jest to skomplikowane 260-metrowe urządzenie wykorzystujące najnowsze rozwiązania technologiczne. Laser ten produkuje wysokiej jakości wiązkę laserową. Ponieważ FLASH jest projektem komercyjnym, każdy zastój urządzenia wiąże się ze stratami finansowymi, Zadaniem oprogramowania nadzorującego pracę podsystemów akceleratora jest wydłużenie czasu jego poprawnej pracy. Zakłada się, że ten cel może być osiągnięty za pomocą automatyzacji rutynowych zadań wykonywanych przez operatorów oraz opracowania oprogramowania usuwającego symptomy drobnych awarii. Zagadnienia poruszane w artykule dotyczą opracowania metodyki i zestawu narzędzi do projektowania i implementacji oprogramowania automatyzującego. Prezentowane podejście i narzędzia omawiane są w kontekście systemu automatyzacji pojedynczej stacji zasilania lasera FLASH.
EN
Algorithmic state machines ASM are one of formal methods of embedded systems specification. They are defined during system project phase. Potential not detected errors in specification may generate unnecessary costs, and in case of dependable systems they may even have catastrophic causes. The article presents formal verification and analysis method of algorithmic state machines using computer deduction in temporal logic (Model Checking technique). Model checker tools enable automatic verification of system specification by checking consistency between model description and requirements which have to be satisfied in the model. The paper concentrates on NuSMV model checker. Formal verification technique Model Checking is discussed basing on presented case study.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.