While most approaches in formal methods address system correctness, ensuring robustness has remained a challenge. In this paper we present and study the logic rLTL which provides a means to formally reason about both correctness and robustness in system design. Furthermore, we identify a large fragment of rLTL for which the verification problem can be efficiently solved, i.e., verification can be done by using an automaton, recognizing the behaviors described by the rLTL formula $\varphi$, of size at most $\mathcal{O} \left( 3^{ |\varphi|} \right)$, where $|\varphi|$ is the length of $\varphi$. This result improves upon the previously known bound of $\mathcal{O}\left(5^{|\varphi|} \right)$ for rLTL verification and is closer to the LTL bound of $\mathcal{O}\left( 2^{|\varphi|} \right)$. The usefulness of this fragment is demonstrated by a number of case studies showing its practical significance in terms of expressiveness, the ability to describe robustness, and the fine-grained information that rLTL brings to the process of system verification. Moreover, these advantages come at a low computational overhead with respect to LTL verification.
翻译:虽然在正式方法中,大多数方法都涉及系统正确性,但确保稳健性仍然是一项挑战。在本文件中,我们提出并研究rLTL逻辑,它提供了一种手段,正式说明系统设计是否正确和稳健性。此外,我们确定了一个大块rLTL的碎片,可以有效解决核查问题,即核查可以通过使用一个自动图进行,承认rLTL公式所描述的大小最多为$\phal{O}/left(3 ⁇ ⁇ varphi ⁇ \right)美元的行为。一些案例研究表明,美元是美元,是美元,是美元,是美元,是美元,是系统长度,是美元,是用来正式说明准确性。此外,这种结果改进了以前已知的RLT的界限,是用于核查的5 ⁇ varphi{\\right$,更接近LT的束缚值。