Timed verification of the generic architecture of a memory circuit using parametric timed automata

Using a variant of Clariso-Cortadella’s parametric method for verifying asynchronous circuits, we analyse some crucial timing behaviors of the architecture of SPSMALL memory, a commercial product of STMicroelectronics. Using the model of parametric timed automata and model checker HYTECH, we formally derive a set of linear constraints that ensure the correctness of the response times of the memory. We are also able to infer the constraints characterizing the optimal setup timings of input signals. We have checked, for two different implementations of this architecture, that the values given by our model match remarkably with the values obtained by the designer through electrical simulation. Partially supported by project MEDEA+ Blueberries. A preliminary version appeared in the Proceedings of 4th International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS’06), Sept. 2006.     

Enzymatic competition: Modeling and verification with timed hybrid petri nets

The formalism of hybrid functional petri nets (HFPN) has proved its convenience for simulating biological systems. The drawback of the noticeable expressiveness of HFPN is the difficulty to perform formal verifications of dynamical properties. In this article, we propose a model-checking procedure for timed hybrid petri nets (THPN), a sub-class of HFPN. This procedure is based on the translation of the THPN model and of the studied property into real-time automata. It is applied to model enzymatic competitions existing in amphibian metamorphosis.     

Case study on distributed and fault tolerant system modeling based on timed automata

This article presents the modeling of a distributed fault-tolerant real-time application by timed automata. The application under consideration consists of several processors communicating via a Controller Area Network (CAN); each processor executes an application that consists of fault-tolerant tasks running on top of an operating system (e.g. OSEK/VDX compliant) and using inter-task synchronization primitives. For such a system, a model checking tool (e.g. UPPAAL) can be used to verify the complex time and logical properties formalized as safety or bounded liveness properties (e.g. end-to-end response time considering an occurrence of a fault). The proposed model reduces the size of the state-space by sharing clocks measuring the execution time of the tasks.     

Performance analysis of probabilistic timed automata using digital clocks

Probabilistic timed automata, a variant of timed automata extended with discrete probability distributions, is a modelling formalism suitable for describing formally both nondeterministic and probabilistic aspects of real-time systems, and is amenable to model checking against probabilistic timed temporal logic properties. However, the previously developed verification algorithms either suffer from high complexity, give only approximate results, or are restricted to a limited class of properties. In the case of classical (non-probabilistic) timed automata it has been shown that for a large class of real-time verification problems correctness can be established using an integral model of time (digital clocks) as opposed to a dense model of time. Based on these results we address the question of under what conditions digital clocks are sufficient for the performance analysis of probabilistic timed automata and show that this reduction is possible for an important class of systems and properties including probabilistic reachability and expected reachability. We demonstrate the utility of this approach by applying the method to the performance analysis of three probabilistic real-time protocols: the dynamic configuration protocol for IPv4 link-local addresses, the IEEE 802.11 wireless local area network protocol and the IEEE 1394 FireWire root contention protocol.

Efficient verification of timed automata with BDD-like data structures

We investigate the effect on efficiency of various design issues for BDD-like data structures of TA state space representation and manipulation. We find that the efficiency is highly sensitive to decision atom design and canonical form definition. We explore the two issues in detail and propose to use CRD (Clock-Restriction Diagram) for TA state space representation and present algorithms for manipulating CRD in the verification of TAs. We compare three canonical forms for zones, develop a procedure for quick zone-containment detection, and present algorithms for verification with backward reachability analysis. Three possible evaluation orderings are also considered and discussed. We implement our idea in our tool Red 4.2 and carry out experiments to compare with other tools and various strategies of Red in both forward and backward analysis. Finally, we discuss the possibility of future improvement.     

机器学习安全及隐私保护研究进展

机器学习作为实现人工智能的一种重要方法,在数据挖掘、计算机视觉、自然语言处理等领域得到广泛应用。随着机器学习应用的普及发展,其安全与隐私问题受到越来越多的关注。首先结合机器学习的一般过程,对敌手模型进行了描述。然后总结了机器学习常见的安全威胁,如投毒攻击、对抗攻击、询问攻击等,以及应对的防御方法,如正则化、对抗训练、防御精馏等。接着对机器学习常见的隐私威胁,如训练数据窃取、逆向攻击、成员推理攻击等进行了总结,并给出了相应的隐私保护技术,如同态加密、差分隐私。最后给出了亟待解决的问题和发展方向。     

浅谈网络应用程序的安全性开发

随着计算机网络的迅速发展,越来越多的人在使用互联网。网络应用使人们的生活更加丰富、工作更加便利。然而,网络应用的安全问题也日益凸显其重要性。该文浅谈了网络应用程序的安全性开发。     

HyperTree: a structural approach to web authoring

The expansion of the World Wide Web (WWW) has created an increasing need for tools capable of supporting WWW authors in composing documents using the HyperText Markup Language (HTML). Currently, most web authors use tools which are basically ordinary text editors and have additional features to facilitate the easy and correct use of HTML tags. This approach places the burden on the web author to design and then create the entire web site in a top-down fashion, without any explicit support for the structural design of the site. In this paper we discuss an alternative structural approach to Web authoring, which is based on the use of the HyperTree hypermedia system as the central authoring tool. The advantages of using HyperTree are two-dimensional. Firstly, web authors can manage a web site as a single complete hypermedia database. For example, HyperTree provides facilities like the automatic creation of indices and the discovery of link inconsistencies. Additionally, it organizes the web pages in an easy to understand hierarchy without using any HTML directly. Secondly, web end-users can benefit from the use of HyperTree, since seeking information in structured web sites is generally less disorientating and develops fewer cognitive overheads. ©1997 John Wiley & Sons, Ltd.     

基于XYZ/ADL的异步Web服务组合描述与验证

Web服务组合为研究对象,重点讨论了服务组合中异步通信行为和时间属性的形式化描述和验证.首先,从软件体系结构角度分析Web服务组合,采用基于时序逻辑的XYZ/ADL描述Web服务的交互行为和时间属性;然后,提出一种符合模型检测工具UPPAAL规约的时间异步通信模型TACM;最后,实现了XYZ/RE通信命令到TACM的映...     

A case study on applying formal methods to medical devices: computer-aided resuscitation algorithm

The design and functional complexity of medical devices have increased during the past 50 years, evolving from the use of a metronome circuit for the initial cardiac pacemaker to functions that include electrocardiogram analysis, laser surgery, and intravenous delivery systems that adjust dosage based on patient feedback. As device functionality becomes more intricate, concerns arise regarding efficacy, safety, and reliability. It thus becomes imperative to adopt a standard or methodology to ensure that the possibility of any defect or malfunction in these devices is minimized. It is with these facts in view that regulatory bodies are interested in investigating mechanisms to certify safety-crictical medical devices. These organizations advocate the use of formal methods techniques to evaluate safety-critical medical systems. However, the use of formal methods is keenly debated, with most manufacturers claiming that they are arduous and time consuming.In this paper we describe our experience in analyzing the requirements documents for the computer-aided resuscitation algorithm (CARA) designed by the Resuscitative Unit of the Walter Reed Army Institute of Research (WRAIR). We present our observations from two different angles – that of a nonbeliever in formal methods and that of a practitioner of formal methods. For the former we catalog the effort required by a novice user of formal methods tools to carry out an analysis of the requirements documents. For the latter we address issues related to choice of designs, errors in discovered requirements, and the tool support available for analyzing requirements .     

不同场景的联邦学习安全与隐私保护研究综述

随着大数据不断发展,联邦学习已被广泛应用于各种各样的场景,从而方便人们的生产生活,但该技术给人们带来便利的同时也让用户面临着数据泄露的挑战,因此数据安全成为联邦学习研究的热点问题.通过介绍横向及纵向联邦学习的训练过程,并对该过程的潜在对手及其攻击原因进行研究,从而分类总结了现有的攻击手段,如投毒攻击、对抗攻击及模型逆推攻击等;在两种场景下分类介绍针对几种攻击手段的防御措施,如梯度稀疏化、恶意检测、秘密样本对齐、标签保护、加密共享和扰动共享等,这些方法不仅可以保证参与方的数据安全,也可以保证联合模型的准确率;最后根据对现有技术的研究,总结了现存方法存在的问题及未来的研究方向.     

Verifying a signature architecture: a comparative case study

We report on a case study in applying different formal methods to model and verify an architecture for administrating digital signatures. The architecture comprises several concurrently executing systems that authenticate users and generate and store digital signatures by passing security relevant data through a tightly controlled interface. The architecture is interesting from a formal-methods perspective as it involves complex operations on data as well as process coordination and hence is a candidate for both data-oriented and process-oriented formal methods. We have built and verified two models of the signature architecture using two representative formal methods. In the first, we specify a data model of the architecture in Z that we extend to a trace model and interactively verify by theorem proving. In the second, we model the architecture as a system of communicating processes that we verify by finite-state model checking. We provide a detailed comparison of these two different approaches to formalization (infinite state with rich data types versus finite state) and verification (theorem proving versus model checking). Contrary to common belief, our case study suggests that Z is well suited for temporal reasoning about process models with complex operations on data. Moreover, our comparison highlights the advantages of proving theorems about such models and provides evidence that, in the hands of an experienced user, theorem proving may be neither substantially more time-consuming nor more complex than model checking.     

实时系统时段性质的模型检验

一、前言随着计算机硬件的飞速发展,计算能力和速度大幅度提高,一方面使得计算机技术应用范围不断扩大,另一方面使得计算机系统的规模和复杂性急剧增加,导致系统出错的几率也随之增大。但任何一个错误在某些系统,如:空中运输控制系统、银行财务系统等,往往可能导致重大的经济损失,甚至人员伤亡,如1996年阿波罗5号火箭的爆炸等。显然对这种高安全性系统的正确性要求是极其严格的,在高安全性系统的开发过程中,最为关键的问题是如何在尽可能早的阶段验证设计的正确性。应用计算机系统的最大障碍就是系统的正确性无法保证,因此提高系统的正确性与可靠性变得日益迫切。     

A formal approach for run-time verification of web applications using scope-extended LTL

ContextIn the past decade, the World Wide Web has been subject to rapid changes. Web sites have evolved from static information pages to dynamic and service-oriented applications that are used for a broad range of activities on a daily basis. For this reason, thorough analysis and verification of Web Applications help assure the deployment of high quality applications.ObjectivesIn this paper, an approach is presented to the formal verification and validation of existing web applications. The approach consists of using execution traces of a web application to automatically generate a communicating automata model. The obtained model is used to model checking the application against predefined properties, to perform regression testing, and for documentation.MethodsTraces used in the proposed approach are collected by monitoring a web application while it is explored by a user or a program. An automata-based model is derived from the collected traces by mapping the pages of the application under test into states and the links and forms used to browse the application into transitions between the states. Properties, meanwhile, express correctness and quality requirements on web applications and might concern all states of the model; in many cases, these properties concern only a proper subset of the states, in which case the model is refined to designate the subset of the global states of interest. A related problem of property specification in Linear Temporal Logic (LTL) over only a subset of states of a system is solved by means of specialized operators that facilitate specifying properties over propositional scopes in a concise and intuitive way. Each scope constitutes a subset of states that satisfy a propositional logic formula.ResultsAn implementation of the verification approach that uses the model checker Spin is presented where an integrated toolset is developed and empirical results are shown. Also, Linear Temporal Logic is extended with propositional scopes.Conclusiona formal approach is developed to build a finite automata model tuned to features of web applications that have to be validated, while delegating the task of property verification to an existing model checker. Also, the problem of property specification in LTL over a subset of the states of a given system is addressed, and a generic and practical solution is proposed which does not require any changes in the system model by defining specialized operators in LTL using scopes.     

基于医院信息系统下的医疗数据隐私安全分析及防护策略

本文结合医院信息系统建设的重要意义,在分析医院信息系统下医疗数据隐私安全危险因素的基础上,从安装漏洞扫描系统、建立完善的访问控制机制、安装入侵检测系统（IDS）及数据备份等方面探讨了医院信息系统下医疗数据隐私安全的防护策略.     

基于Yices对时间自动机的有界模型检测

为了避免在有界模型检测过程中对变量进行布尔编码以及对时间自动机模型中的时钟进行预处理,给出一个利用SMT(satisfiability modulo theories)工具进行的对时间自动机进行有界模型检测的方法.该方法将时间自动机模型直接转换成SMT工具可识别的逻辑公式,利用SMT工具可求解包含有整数型和实数型变量逻辑公式的能力来进行模型检测.实验结果表明,对于某些可达性性质的验证,该方法的效率有一定的优势.     

基于着色时间Petri网的实时系统的形式验证

嵌入式实时系统多数应用在安全性要求较高的场合,因此需要保证系统的正确性.复杂性不断增加的实时系统迫切需要在系统开发早期引入形式化分析技术来验证系统的期望性质.时间Petri网是有严格数学基础的图形表达工具,适合对实时系统建模;时间自动机(Timed Automata,TA)有成熟的验证工具,被广泛用于实时系统的模型检验和验证.本文提出一种基于着色时间Petri网(Colored Time Petri Net,CTPN)的实时系统的验证方法,用CTPN对带有控制流和数据流的实时系统建模,通过转换规则将CTPN模型转换成语义等价的TA模型,利用模型检验工具UPPAAL验证系统的性质.最后,用实例证明此方法有效.     

Defeating traffic analysis via differential privacy: a case study on streaming traffic

In this paper, we explore the adaption of techniques previously used in the domains of adversarial machine learning and differential privacy to mitigate the ML-powered analysis of streaming traffic. Our findings are twofold. First, constructing adversarial samples effectively confounds an adversary with a predetermined classifier but is less effective when the adversary can adapt to the defense by using alternative classifiers or training the classifier with adversarial samples. Second, differential-privacy guarantees are very effective against such statistical-inference-based traffic analysis, while remaining agnostic to the machine learning classifiers used by the adversary. We propose three mechanisms for enforcing differential privacy for encrypted streaming traffic and evaluate their security and utility. Our empirical implementation and evaluation suggest that the proposed statistical privacy approaches are promising solutions in the underlying scenarios

     

Analysis of a biphase mark protocol with Uppaal and PVS

The biphase mark protocol is a convention for representing both a string of bits and clock edges in a square wave. The protocol is frequently used for communication at the physical level of the ISO/OSI hierarchy, and is implemented on microcontrollers such as the Intel 82530 Serial Communications Controller. An important property of the protocol is that bit strings of arbitrary length can be transmitted reliably, despite differences in the clock rates of sender and receiver (drift), variations of the clock rates (jitter), and distortion of the signal after generation of an edge. In this article, we show how the protocol can be modelled naturally in terms of timed automata. We use the model checker Uppaal to derive the maximal tolerances on the clock rates, for different instances of the protocol, and to support the general parametric verification that we formalized using the proof assistant PVS. Based on the derived parameter constraints we propose instances of BMP that are correct (at least in our model) but have a faster bit rate than the instances that are commonly implemented in hardware.F.W. Vaandrager was supported by EU IST project IST-2001-35304 Advanced Methods for Timed Systems (AMETIST).lA.L. de Groot was supported by NWO project 612.062.000 Architecture for Structuring the requirements Specification of Embedded Safety-critical Systems (ASSESS).