验证Java程序的临时规范外文翻译资料

Verifying temporal specifications of Java programs

·Luca Spalazzi ·Giovanni Liva ·Martin Pinzger ·

Andreas Bollin²

1 Motivation

Nowadays, more and more software is being developed whose behavior depends on time and on the satisfaction of given time constraints. Consequently, the most popular programming languages provide APIs to represent and manipulate time. This obviously represents a further possible source of flaws, as shown by some recent cases such as, for example, the two vulnerabilities discovered in the Linux kernel due to timestamp overflows or several time-related errors discovered in Java software (Liva et al. 2018). It is, therefore, essential to have verification tools to discover such flaws, and even better if this can be done by directly analyzing the code.

This work focuses on software model checking of timed specifications. This means extracting a software model that, in this case, takes into account time (expressed as timestamps, durations, and other time constraints). We express such models as timed automata (Alur et al. 1990), i.e. finite automata extended with real-valued clocks that can be reset and must satisfy given clock constraints; for these reasons they are appropriate for modeling continuous time systems, in particular real-time systems. We aim at verifying programs written in Java, one of the most popular programming languages to date. Despite the widespread use of Java and the growing importance of time-dependent behaviors, only few authors (e.g., see Liva et al. (2017), Luckow et al. (2015), Schoeberl et al. (2010), and Boslash;gholm et al. (2008)) focused on timed automata extraction from Java programs. Furthermore, these few works studied exclusively how to extract control flow automata, i.e., automata that follow the program control flow but do not take into account the state space formed by program variables. This results in an over-approximation of the program behavior, which precludes the possibility of verifying properties over program variables in various program states and, in particular, those properties that depend on variables ranging over time values such as timestamps and durations. For this reason, most of them aim at performing best-/worst-case execution time analysis (WCET/BCET) or schedulability.

This paper tries to fill the gap described above and proposes a verification methodology based on software model checking to establish the correctness of Java programs w.r.t. specifications depending on real-valued clocks. We also show that the methodology can effectively tackle real-world Java projects and it is able to detect very subtle bugs in Apache

Kafka, a distributed streaming platform, and Alluxio, a cloud storage abstraction library. The proposed methodology has the following innovative contributions:

– A formal semantics for timed features of Java (Section 5). In this respect, we consider the following three features: (1) pausing the execution for a limited amount of time, (2) waiting for an event that has to occur before a deadline expires, and (3) comparing timestamps.

– A set of rules used to build a network of timed automata from concurrent and timedependent Java programs (Section 6). In this respect, we exploit an SMT solver.

– A proof which shows that the produced network of timed automata preserves the correctness of the original Java program w.r.t. the considered family of timed specifications (Section 7).

A previous version of this work (Spalazzi et al. 2018) showed some core components of our approach. In this work, we extend the translation rules, we prove the soundness of the produced network of timed automata, and we apply it to more software projects.

In Section 2, we draw some connections between the relevant work in the area and our methodology. Section 3 introduces some theoretical backgrounds to make the rest of the work self-contained. In Section 4, we introduce some inherent limitations of software model checking that have an impact on the design choices behind the presented verification methodology. In Section 5, we formally define a semantics for the time-dependent aspects of the Java language. In Sections 6 and 7, we present the rules for extracting timed automata from Java threads and show the soundness of the approach. In Section 8, we show the applicability of our methodology to discover bugs in a running example as well as two real-world Java projects used as workbenches for the methodology itself. In particular, we show that the methodology can be helpful to discover previously unknown bugs in the software, and that such bugs are often difficult to discover by traditional test-based approaches. For our experiments, Uppaal is used to verify the timed automata networks obtained with our tool (Larsen et al. 1997). In Section 9, we collect some concluding remarks and suggest future research directions stemming from the presented work.

2 Related work .

With the term temporal property, and its derivatives such as temporal logic, we refer to all those properties that depend on how a system evolves over time. Linear Temporal Logic (LTL) and Computation Tree Logic (CTL) are examples of temporal logics to represent these types of properties. With the term timed temporal properties, and derivatives such as timed temporal logic, we refer to all those properties that refer to real time and constrain the values that timestamps and durations can take. Metric Temporal Logic (MTL) and Timed Computation Tree Logic (TCTL) are examples of timed temporal logics.

Software verification techniques can be classified (Jhala and Majumdar 2009; Drsquo;silva et al. 2008) into techniques that are able to work with either a concrete or an abstract software representation.

The term concrete indicates that such techniques are able to r

剩余内容已隐藏，支付完成后下载完整资料

验证Java程序的时态规范 卢卡·斯帕拉齐·乔瓦尼·利瓦·马丁·平茨格 安德烈亚斯·博林

1动机

现在越来越多的软件被开发出来，其行为依赖于时间和满足给定的时间约束。因此，最流行的编程语言提供了表示和操作时间的api。这显然是缺陷的另一个可能来源，如最近的一些案例所示，例如，Linux内核中发现的两个漏洞是由于时间戳溢出或Java软件中发现的几个时间相关错误造成的（Liva et al.2018）。因此，有必要使用验证工具来发现这些缺陷，如果可以通过直接分析代码来实现这一点就更好了。

本文主要研究定时规范的软件模型检查。这意味着提取一个软件模型，在这种情况下，它考虑了时间（表示为时间戳、持续时间和其他时间约束）。我们将此类模型表示为时间自动机（Alur et al.1990），即扩展了实值时钟的有限自动机，这些时钟可以重置，并且必须满足给定的时钟约束；由于这些原因，它们适合于对连续时间系统，特别是实时系统进行建模。我们的目标是验证用Java编写的程序，Java是迄今为止最流行的编程语言之一。尽管Java的广泛使用和依赖时间的行为越来越重要，但只有少数作者（例如，见Liva et al.（2017）、Luckow et al.（2015）、Schoeberl et al.（2010）和Boslash;gholm et al.（2008））专注于从Java程序中提取时间自动机。此外，这几项工作专门研究如何提取控制流自动机，即遵循程序控制流但不考虑程序变量形成的状态空间的自动机。这导致程序行为的过度近似，这排除了在各种程序状态下验证程序变量属性的可能性，特别是那些依赖于随时间变化的变量值（如时间戳和持续时间）的属性。由于这个原因，它们中的大多数旨在执行最佳/最坏情况下的执行时间分析（WCET/BCET）或可调度性。

本文试图填补这一空白，提出了一种基于软件模型检查的验证方法，以确定Java程序w.r.t.规范的正确性是否依赖于实值时钟。我们还表明，该方法能够有效地处理现实世界中的Java项目，并且能够检测到分布式流媒体平台apachekafka和云存储抽象库Alluxio中非常细微的错误。拟议的方法有以下创新贡献：

–Java定时特性的正式语义（第5节）。在这方面，我们考虑以下三个特性：（1）暂停执行一段有限的时间，（2）等待在截止日期到期之前必须发生的事件，以及（3）比较时间戳。

–一组用于从并发和时间相关的Java程序构建时间自动机网络的规则（第6节）。在这方面，我们开发了一个SMT求解器。

–证明生成的时间自动机网络保留了原始Java程序w.r.t.的正确性，即所考虑的时间规范系列（第7节）。

这项工作的前一个版本（Spalazzi等人，2018年）展示了我们方法的一些核心组成部分。在这项工作中，我们扩展了转换规则，证明了所生成的时间自动机网络的可靠性，并将其应用到更多的软件项目中。

在第2节中，我们将在该领域的相关工作和我们的方法之间建立一些联系。第三节介绍了一些理论背景，使后面的工作更加完整。在第4节中，我们介绍了软件模型检查的一些固有局限性，这些局限性对所提出的验证方法背后的设计选择有影响。在第5节中，我们正式定义了Java语言的时间相关方面的语义。在第6节和第7节中，我们介绍了从Java线程中提取时间自动机的规则，并展示了该方法的合理性。在第8节中，我们将展示我们的方法在一个正在运行的示例中发现bug的适用性，以及作为方法本身工作台的两个真实的Java项目。特别地，我们证明了这种方法有助于发现软件中以前未知的bug，并且这种bug通常很难通过传统的基于测试的方法来发现。在我们的实验中，Uppaal被用来验证用我们的工具获得的时间自动机网络（Larsen等人，1997）。在第九节，我们收集了一些结论，并提出了未来的研究方向。

2相关工作。

对于术语“时态属性”及其派生词（如时态逻辑），我们指的是所有那些依赖于系统如何随时间演化的属性。线性时态逻辑（LTL）和计算树逻辑（CTL）是表示这些类型属性的时态逻辑的例子。使用术语定时时态属性，以及诸如定时时态逻辑之类的派生，我们指代所有那些涉及实时并约束时间戳和持续时间可以采用的值的属性。度量时态逻辑（MTL）和定时计算树逻辑（TCTL）是定时时态逻辑的例子。

软件验证技术可以分为（Jhala and Majumdar 2009；Dsilva et al.2008）能够处理具体或抽象软件表示的技术。

术语具体表示这种技术能够准确地表示程序状态（图1b）。这种方法，即使看起来很吸引人，但只要存在无限（或非常大）的状态空间，就不可行，在许多实际情况下，软件通常就是这样。为了避免不可行，需要在时间/空间复杂性和完整性之间进行权衡。

特别是，使用了基于欠近似抽象的技术，例如系统执行探索（Godefroid 1997；Havelund and Pressburger 2000；Liva et al.2018），一种“面向伪造”的动态分析（Jhala and Majumdar 2009）。换言之，这是合理的，即没有产生虚假的反例，但不完整，即一些反例可能检测不到（Godefroid 2004）。运行时验证也存在类似的情况（Bauer et al.2011），将正式规范与实际软件执行进行比较。但是，在这种情况下，没有提取要测试的软件模型。

一种不同的方法是通过过度近似抽象来表示，例如，状态空间抽象，其中具体的状态空间被划分为等价类，使得每个类都是一个抽象状态（Ball and Rajamani 2002；Beyer et al.2007；Corbett et al.2000；Heizmann et al.2013；Herber et al.2008；Kung et al.1994；Liva等人，2017年；Pu等人，2006年；Sen和Mall，2016年）。这种抽象是“面向验证的”（Jhala和Majumdar 2009），也就是说，在指定的抽象级别上找到所有反例是完整的，但它是不健全的，因为它可能产生虚假的反例（Clarke et al.1994）。为了减少反例的数量，需要某种反例引导的抽象精化（Clarke等人，2000），其中抽象模型是迭代和自动精化的。已经提出了“非计时”自动机（Clarke et al.2000）和时间自动机（Wang and Jiao 2014）的几种技术。

综上所述，正如Jhala和Majumdar（2009）所明确指出的，过度近似抽象可以证明软件的正确性（在抽象是健全的w.r.t.代码的条件下），而在近似抽象下，特别是系统测试，只能推测它。它只能揭示虫子的存在，而不能揭示虫子的缺失（这与著名的Dijkstra的句子（dijkstra1969）是一致的）。

关于超近似抽象技术，两种经典的技术是谓词抽象和控制流抽象。

通过谓词抽象，等价类（即抽象状态）是使用程序变量子集上的谓词创建的（图1c）。这意味着每个抽象状态都由这些谓词的布尔组合表示，这些谓词过于近似于程序的可到达具体状态（Beyer和Wendler 2012）。这种抽象计算通常使用可满足性模理论（SMT）求解器来完成（Armando et al.2009；Ball and Rajamani 2002；Beyer et al.2007；Beyer and Keremoglu 2011；Clarke et al.2005；Corbett et al.2000；Cordeiro et al.2011；Kahsai et al.2016；Kung et al.1994；Sen and Mall 2016）。实际上，一个大的具体状态集可以被折叠成一个单一的抽象状态，由这些具体状态所满足的谓词集（通常很小）表示。

对于控制流抽象，等价类由程序位置表示（见图1d）：每个程序位置都存在一个抽象状态，即每个程序语句（Heizmann et al.2013；Herber et al.2008；Liva et al.2017；Pu et al.2006）。因此，程序变量被抽象出来，抽象的状态空间与程序位置集相吻合。因此，抽象状态空间可以非常快速地计算（不需要涉及SMT求解器），代价是一些程序属性无法验证。

应该注意的是，为了定义这些技术，它们必须引用所讨论的编程语言的语义，而不仅仅是它们的语法。关于Java，Bogdanas和Roscedil;u（2015）首先对多线程Java的语法和语义进行了定义。在他们的工作中，Java的语义是通过K-framework来定义的，K-framework是一个模块化的工程语言语义框架，基于一组对配置的约简规则。配置是程序状态的组合和可扩展的代数结构。我们扩展了他们的工作，在考虑时间语义的配置中引入了新的信息。

一些作者（Herber，2008； Liva，2017）建议从通用编程语言中提取控制流定时自动机，但这样做并没有考虑程序变量在执行过程中所扮演的角色。 因此，这些作品无法检查查看程序变量状态的规范。 其他人则专注于可调度性分析和最佳或最坏情况下的执行时间（Luckow等人，2015年； Thomsen等人，2015年； Schoeberl等人，2010年；Boslash;gholm等人，2008年），但他们并未考虑该程序的正确性。 .wrt 属性取决于时间戳和持续时间范围内的变量。 据我们所知，没有人考虑过模型检查时间属性的问题，即Java代码的时间属性也依赖于时间戳和持续时间变量。 本文中介绍的方法填补了这一空白，当将其应用于复杂软件系统时，我们将其在现实世界项目中的某些应用作为其适用性和实用性的一个论据。

赫伯（Herber）等人。 （2008）对SystemC程序进行模型检查，从中提取定时自动机。 他们还假设大多数指令具有零时模型。 他们的方法只能处理包含对数字变量进行数学运算的程序。 我们的方法克服了这一限制，可以应对用户定义的数据类型和方法。

Blast（Beyer等人，2007）和Ultimate LTLAutomizer（Dietsch等人，2015）将模型检查应用于C程序。 Blast从C函数中提取未定时的控制流自动机； 它只能检查程序位置的可达性； 并且仅处理Integer和Boolean程序变量。 Ultimate LTLAutomizer使用SMT求解器选择路径的有限前缀，并在考虑完整的无限路径之前检查其不可行。 因此，它能够验证活动性的严格子集。 但是，它们都限制了源代码中预定义错误位置的可达性，并且规范不能考虑实际值的时钟及其相关约束。

Java PathFinder（JPF）（Havelund和Pressburger 2000; Cuong和Cheng 2008），其演变的Symbolic PathFinder（SPF）（Pas˘areanu和Rungta˘2010）和Bandera（Corbett等2000）是Java程序的流行模型检查器。 JPF使用Java虚拟机，该虚拟机探索正在分析的Java字节码的符号路径。 SPF使用约束求解器从Java字节码生成模型。 Bandera采用程序切片技术来抽象化不会影响已验证规范的程序变量。 这三个都没有从Java代码中提取定时自动机，因此，它们仅允许分析“非定时”时态属性。 即，根据我们上面提供的含义，可以检查LTL中的属性，但不能检查MTL或TCTL中的属性。

诸如CPAChecker（Beyer和Keremoglu，2011）和SeaHorn（Gurfinkel等，2015）等更新的软件验证方法提供了一个模块化的环境，在该环境中，程序可以通过多个阶段进行操作，以形成某种验证“管道”。 它们在内部实现方面有所不同，例如CPAChecker使用Control-Flow自动机作为源代码的中间表示，而SeaHorn将输入程序转换为Constrained Horn子句。 然后，两者都允许对程序的中间表示进行后处理，以使用户可以为每个程序选择不同的验证策略。 通常，最后一步是在几个可用的SMT求解器中使用一个，以伪造输入（可达性）规范。 即使在这种情况下，我们的方法也是创新的，因为我们的目标是以MTL或TCTL表示的实时时间规范。

SymRT（Luckow et al。2015）是一种基于SPF的工具，可从Java代码中提取定时自动机网络，旨在验证TCTL中表示的可达性以及WCET / BCET和可调度性分析。 SymRT使用控制流抽象，因为它仅旨在验证实时属性，而无需考虑程序变量产生的状态空间。 在我们的工作中，我们使用谓词抽象并考虑程序（尤其是时间）变量，从而验证了更广泛的规范集。

Sen and Mall（2016）应用了几种静态分析工具对Java字节码中的有限状态模型进行逆向工程，主要用于文档目的。 w.r.t.的主要区别 我们的方法是，他们既不在模型中也不在规范中处理时间，而是为程序中的每个对象计算一个过渡系统。 这意味着他们基于类的私有属性的抽象状态来计算每个类的状态空间，并计算方法调用如何将对象从一个抽象状态移动到另一个抽象状态。 程序的有限状态模型是程序本身中使用的对象的转换系统的组合而获得的。 我们有兴趣采用这种技术来抽象线程所使用的对象，但是我们声称描述线程所采取的中间步骤的顺序还不够好（例如，我们可能需要知道线程以什么顺序获取其资源。 以检测死锁情况）。

3理论背景

为了自洽，让我们在这里收集几个正式定义，这些定义将在本文的其余部分中使用。

3.1定时自动网络

让我们假设时钟变量C的有限集合。我们将时间约束TC（C）称为语法项：〜isin;{le;=，ge;} TC（C）:: = | not;TC（C）| TC（TC是时域。在下面，）or;TC（C）| C〜C | C〜T，其中lt;，，，gt;是比较运算符，我们假设时域为：→T将时钟变量与其在域连续集中的时间值相关联（例如T =Rge;0）。 让我们将时钟

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[603625]，资料为PDF文档或Word文档，PDF文档可免费转换为Word