检索结果-内蒙古大学图书馆

Current-State Opacity Formulations in Probabilistic Finite Automata

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2014年第1期59卷 120-133页

作者： Saboori, Anooshiravan Hadjicostis, Christoforos N. Univ Illinois Coordinated Sci Lab Dept Elect & Comp Engn Urbana IL 61801 USA Univ Cyprus Dept Elect & Comp Engn CY-1678 Nicosia Cyprus

A system is said to be current-state opaque if the entrance of the system state to a set of secret states remains opaque (uncertain) to an intruder-at least until the system leaves the set of secret states. This notion of opacity has been studied in nondeterministic finite automata settings (where the intruder observes a subset of events, for example, via some natural projection mapping) and has been shown to be useful in characterizing security requirements in many applications (including encryption using pseudorandom generators and coverage properties in sensor networks). One limitation of the majority of existing analysis is that it fails to provide a quantifiable measure of opacity for a given system;instead, it simply provides a binary characterization of the system (being opaque or not opaque). In this paper, we address this limitation by extending current-state opacity formulations to systems that can be modeled as probabilistic finite automata under partial observation. We introduce three notions of opacity, namely: 1) step-based almost current-state opacity;2) almost current-state opacity;and 3) probabilistic current-state opacity, all of which can be used to provide a measure of a given system's opacity. We also propose verification methods for these probabilistic notions of opacity and characterize their corresponding computational complexities.

关键词： Automata discrete event systems (DES) Markov processes opacity verification complexity

来源：评论

学校读者我要写书评

暂无评论

Proof-labeling schemes: Broadcast, unicast and in between

引用

THEORETICAL COMPUTER SCIENCE 2022年 923卷 179-195页

作者： Patt-Shamir, Boaz Perry, Mor Tel Aviv Univ Sch Elect Engn Tel Aviv Israel Acad Coll Tel Aviv Yaffo Sch Comp Sci Tel Aviv Israel

We study the effect of limiting the number of different messages a node can transmit simultaneously on the verification complexity of proof-labeling schemes (PLS). In a PLS, each node is given a label, and the goal is to verify, by exchanging messages over each link in each direction, that a certain global predicate is satisfied by the system configuration. We consider a single parameter rthat bounds the number of distinct messages that can be sent concurrently by any node: in the case r = 1, each node may only send the same message to all its neighbors (the broadcast model), in the case r >= Delta, where Delta is the largest node degree in the system, each neighbor may be sent a distinct message (the unicast model), and in general, for 1 <= r <= Delta, each of the r messages is destined to a subset of the neighbors. We show that message compression linear in r is possible for verifying fundamental problems such as the agreement between edge endpoints on the edge state. Some problems, including verification of maximal matching, exhibit a large gap in complexity between r = 1 and r > 1. For some other important predicates, the verification complexity is insensitive to r, e.g., the question whether a subset of edges constitutes a spanningtree. We also consider the congested clique model. We show that the crossing technique [1] for proving lower bounds on the verification complexity can be applied in the case of congested clique only if r = 1. Together with a new upper bound, this allows us to determine the verification complexity of MST in the broadcast clique. Finally, we establish a general connection between the deterministic and randomized verification complexity for any given number r. (c) 2022 Elsevier B.V. All rights reserved.

关键词： verification complexity Proof-labeling schemes CONGEST model Congested clique

来源：评论

学校读者我要写书评

暂无评论

A multiple-valued logic approach to the design and verification of hardware circuits

引用

JOURNAL OF APPLIED LOGIC 2016年 15卷 69-93页

作者： Rosenmann, Amnon Graz Univ Technol Inst Discrete Math Steyrergasse 30 A-8010 Graz Austria

We present a novel approach, which is based on multiple-valued logic (MVL), to the verification and analysis of digital hardware designs, which extends the common ternary or quaternary approaches for simulations. The simulations which are performed in the more informative MVL setting reveal details which are either invisible or harder to detect through binary or ternary simulations. In equivalence verification, detecting different behavior under MVL simulations may lead to the discovery of a genuine binary non-equivalence or to a qualitative gap between two designs. The value of a variable in a simulation may hold information about its degree of truth and its "place of birth" and "date of birth". Applications include equivalence verification, initialization, assertions generation and verification, partial control on the flow of data by prioritizing and block-oriented simulations. Much of the paper is devoted to theoretical aspects behind the MVL approach, including the reason for choosing a specific algebra for computations and the introduction of the notions of De Morgan Canonical Form and of verification complexity of Boolean expressions. Two basic simulation-based algorithms are presented, one for satisfying and verifying combinational designs and the other for equivalence verification of sequential designs. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Multiple-valued logic Hardware verification Hardware simulation verification complexity De Morgan Canonical Form

来源：评论

学校读者我要写书评

暂无评论

Current-State Opacity Formulations in Probabilistic Finite Automata (vol 59, pg 120, 2014)

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第5期69卷 3480-3481页

作者： Saboori, Anooshiravan Hadjicostis, Christoforos N. Snowflake Inc San Mateo CA 94402 USA Univ Cyprus Dept ECE CY-1678 Nicosia Cyprus

This note identifies a flaw in the proof of Theorem 16 in (Saboori and Hadjicostis, 2014). It also discusses how the statement of Theorem 16 can be adjusted and provides the corresponding proof.

关键词： Automata discrete event systems (DES) Markov processes opacity verification complexity

来源：评论

学校读者我要写书评

暂无评论

The Execution Migration Machine: Directoryless Shared-Memory Architecture

引用

COMPUTER 2015年第9期48卷 50-59页

作者： Shim, Keun Sup Lis, Mieszko Khan, Omer Devadas, Srinivas DE Shaw Res New York NY 10036 USA Univ British Columbia Dept Elect & Comp Engn Vancouver BC V5Z 1M9 Canada Univ Connecticut Dept Elect & Comp Engn Storrs CT USA MIT Elect Engn & Comp Sci Cambridge MA 02139 USA

For certain applications involving chip multiprocessors with more than 16 cores, a directoryless architecture with fine-grained and partial-context thread migration can outperform directory-based coherence, providing ... 详细信息

关键词： microprocessor chips shared memory systems chip multiprocessors directoryless shared-memory architecture execution migration machine fine-grained thread migration partial-context thread migration verification complexity Cache memory Distributed databases Instruction sets Parallel processing Program processors Protocols Software architecture System-on-chip data locality distributed caches hardware parallel architectures shared memory thread migration

来源：评论

学校读者我要写书评

暂无评论

A Comparative Study of Insertion Sorting Algorithm verification 2

A Comparative Study of Insertion Sorting Algorithm Verificat...

引用

2017 IEEE 2nd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC 2017)

作者： Dongchen Jiang Miao Zhou School of Information Science & Technology Beijing Forestry University

ISBN: (纸本)9781509064151;9781509064144

Focusing on the impact different ways of formalization have on the according verifications of sorting algorithm,this paper presents the formal specifications of insertion sort,and verifies its functional correctness using Isabelle/HOL. For the formalization, the value-based method and the index-based method are compared, which turns out that the index-based method is more suitable for verification in various aspects.

关键词： algorithm verification insertion sort algorithm specification verification complexity

来源：评论

学校读者我要写书评

暂无评论

A Method of Logically Time Synchronization for Safety-critical Distributed System 18

A Method of Logically Time Synchronization for Safety-critic...

引用

18th International Conference on Advanced Communication Technology (ICACT)

作者： Park, Jeman Kim, Taeho Elect & Telecommun Res Inst Daejeon South Korea

ISBN: (纸本)9788996865063

Legacy real-time and embedded systems have been small scale and standalone. However, recently they are increasingly being connected to create large-scale distributed system. Such distributed embedded system is realized in automotive, medical, and manufacturing automation. Also, there are many researches about software platform for large-scale distributed system. verification of the application is required in SW platform for safety-critical distributed system. However, the verification complexity increases in practice as several factors such as delay, jitter and error. An equivalent synchronized execution of distributed tasks are required in distributed real-time system. Our method is based on the PALS (Physically Asynchronous Logically Synchronous) which is a complexity-reducing architectural pattern for distributed real-time systems. It allows developers to design, verify and implement a logically synchronous implementation of real-time distributed applications. In this paper, we introduce a logical time synchronization for reducing complexity between distributed nodes in distributed embedded system. It make verification and development of distributed software easier. It is helpful to develop distributed embedded system which requires safety and reliability. This paper is useful for application programmer or system manager who wants to establish distributed embedded system which requires safety and reliability.

关键词： Logical Time Synchronization PALS Middleware Safe-Critical System verification complexity

来源：评论

学校读者我要写书评

暂无评论

Polynomial Word-Level verification of Arithmetic Circuits 21

Polynomial Word-Level Verification of Arithmetic Circuits

引用

19th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE)

作者： Barhoush, Mohammed Mahzoon, Alireza Drechsler, Rolf Univ Bremen Inst Comp Sci Bremen Germany DFKI GmbH Cyber Phys Syst Bremen Germany

ISBN: (纸本)9781450391276

Verifying the functional correctness of a circuit is often the most time-consuming part of the design process. Recently, world-level formal verification methods, e.g., Binary Moment Diagram (BMD) and Symbolic Computer Algebra (SCA) have reported very good results for proving the correctness of arithmetic circuits. However, these techniques still frequently fail due to memory or time requirements. The unknown complexity bounds of these techniques make it impossible to predict before invoking the verification tool whether it will successfully terminate or run for an indefinite amount of time. In this paper, we formally prove that for integer arithmetic circuits, the entire verification process requires at most linear space and quadratic time with respect to the size of the circuit function. This is shown for the two main word-level verification methods: backward construction using BMD and backward substitution using SCA. We support the architectures which are used in the implementation of integer polynomial operations, e.g., X-3 - XY2 + XY. Finally, we show in practice that the required space and run times of the word-level methods match the predicted results in theory when it comes to the verification of different arithmetic circuits, including exponentiation circuits with different power values (X-P : 2 <= P <= 7) and more complicated circuits (e.g., X-2 + XY + X).

关键词： formal verification verification complexity symbolic computer algebra binary moment diagrams

来源：评论

学校读者我要写书评

暂无评论

Proof-Labeling Schemes: Broadcast, Unicast and in Between 1

引用

19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)

作者： Patt-Shamir, Boaz Perry, Mor Tel Aviv Univ Sch Elect Engn IL-6997801 Tel Aviv Israel

ISBN: (数字)9783319690841

ISBN: (纸本)9783319690841;9783319690834

We study the effect of limiting the number of different messages a node can transmit simultaneously on the verification complexity of proof-labeling schemes (PLS). In a PLS, each node is given a label, and the goal is to verify, by exchanging messages over each link in each direction, that a certain global predicate is satisfied by the system configuration. We consider a single parameter r that bounds the number of distinct messages that can be sent concurrently by any node: in the case r = 1, each node may only send the same message to all its neighbors (the broadcast model), in the case r >= Delta, where is the largest node degree in the system, each neighbor may be sent a distinct message (the unicast model), and in general, for 1 <= r <= Delta, each of the r messages is destined to a subset of the neighbors. We show that message compression linear in r is possible for verifying fundamental problems such as the agreement between edge endpoints on the edge state. Some problems, including verification of maximal matching, exhibit a large gap in complexity between r = 1 and r > 1. For some other important predicates, the verification complexity is insensitive to r, e.g., the question whether a subset of edges constitutes a spanning-tree. We also consider the congested clique model. We show that the crossing technique [5] for proving lower bounds on the verification complexity can be applied in the case of congested clique only if r = 1. Together with a new upper bound, this allows us to determine the verification complexity of MST in the broadcast clique.

关键词： verification complexity Proof-labeling schemes CONGEST model Congested clique

来源：评论

学校读者我要写书评

暂无评论

Cooperative Game Model of Delegation Computing: Verifier Separated from Calculators

Cooperative Game Model of Delegation Computing: Verifier Sep...

引用

39th IEEE International Conference on Computer Communications (IEEE INFOCOM)

作者： Zhang, Duo Tian, Youliang Wang, Linjie Gao, Sheng Ma, Jianfeng Guizhou Univ State Key Lab Publ Big Data Coll Comp Sci & Technol Coll Math & Stat Guiyang Peoples R China Guizhou Univ State Key Lab Publ Big Data Coll Comp Sci & Technol Inst Cryptog & Date Secur Guiyang Peoples R China Guizhou Univ State Key Lab Publ Big Data Coll Comp Sci & Technol Guiyang Peoples R China Cent Univ Finance & Econ Sch Informat Beijing Peoples R China Xidian Univ Sch Cyber Engn Coll Comp Sci & Technol Xian Peoples R China

ISBN: (纸本)9781728186955

In cloud computing, the delegation computation service is required because end users usually are resource constrained, and at the same time the correctness of computing results needs to be verified. However, all the existing and available technologies have a high cost to verify which is the main problem faced by the delegation computing under the cloud platform. In order to address this issue, based on the game theory and a smart contract, we construct three protocols. The client and the calculator sign the Prisoner's Protocol to incentivize correct computation by asking the calculator to pay a deposit upfront;The client and the verifier sign the Long-acting Mechanism Protocol to ensure the validity of the verification results;The calculator and the verifier sign the Collusion Protocol to make collusion the most profitable strategy for all colluding parties. Through the combination of these protocols, the work is realized by separation the computing task and the verification task, and the heavy verification task is avoided. Finally, the performance analysis of the results shows that the combination of all the protocols not only solves the problem of verification complexity in the traditional delegation computing, but also guarantees the benefit of the honest player.

关键词： Cloud computing Smart contract Game theory Rational delegation computing verification complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：