基于交互式马尔可夫链的可信动态度量研究

可信动态度量为保障可信计算平台的可靠运行提供了重要支撑.根据系统的可靠性、可用性、信息和行为安全性,提出了可信度量要达到的目标.当前的可信度量集中在可信功能度量上,基于交互式马尔可夫链增加性能特征指标度量,即在预期行为描述模型中,运用变迁系统模型描述功能预期,通过将体现在可靠性上的路径概率与预期的关联,获取完成特定行为...     

基于静态马尔可夫链模型的实时异常检测

马尔可夫链模型可以用来描述系统的正常行为模式,文中提出了一种基于静态马尔可夫链的异常检测方法,在此基础上进行了算法实现。实验结果表明该方法实现简单,准确率较高,可适用于不同环境下的实时检测。     

基于MATLAB的隐马尔可夫模型识别CpG岛

随着多数生物基因组测序工作的完成,基因识别就显得尤为重要.CpG岛在基因组中有着重要的生物学意义,而识别CpG岛将有助于基因的识别.因此构建了识别DNA序列中CpG岛的隐马尔可夫模型HMM(Hidden Markov Model),并利用网上人类基因CpG岛数据库中随机选取的94条基因序列数据对该模型进行训练与检测,得到了很高的预测准确率,结果表明HMM用于CpG岛的识别是快速有效的.     

基于马尔可夫链的市场营销预测模型

本文通过建立产品的状态转移概率矩阵,利用马尔可夫链进行分析和计算,给出产品的市场营销预测的数学模型,从而给经济预测提供切实可靠的理论依据,并且运用Excel软件实现马尔可夫预测技术.设计的程序使用方便,操作简单,大大提高了工作效率,具有一定的实用和推广价值.     

基于马尔可夫链的性能检测器的设计与实现

为了可视化建模和验证并发系统的性能,设计并实现了一个以交互式马尔可夫链为数学原型的性能检测器.对该软件的系统结构、数据结构和功能模块等进行了探讨和设计,并举例验证.该软件采用Java Swing界面编程技术,支持图形化建模系统和撰写逻辑公式,界面友好,易于操作.     

基于马尔可夫链的交通分配模型及应用

以吸引马尔可夫链为理论基础，在广义出行路径意义下，给出了交通量在路网节点间的一步转移概率矩阵，并以此为依据，得到了在给定Ｏ－Ｄ量下交通分配算法。最后的算例表明了模型及算法的实用价值。     

基于特征模式的马尔可夫链异常检测模型

为提高检测精度,同时保持算法复杂度在可接受范围内,提出基于特征模式的马尔可夫链异常检测模型。提取所有支持度大于阈值的系统调用短序列为特征模式,在此基础上建立改进的马尔可夫模型CPMC。在检测时,用程序轨迹匹配特征模式,计算其在CPMC模型下的概率,概率小则代表异常。实验表明,该方法的检测精度高于目前常见的几种单一方法,与DBCPIDS方法的精度近似相等,但其计算复杂度更低。     

基于马尔可夫链与服务质量的网络可用性

针对网络可用性在不同网络业务中的服务质量（QoS）存在差异,且与性能花费相互制约的问题,引入了马尔可夫链理论,在定义了基于业务开销最小的服务能力匹配度的基础上构建了基于马尔可夫链和QoS指标的网络可用性（MCQNA）评价模型。首先,从最能反映网络可用特征的QoS指标出发,兼顾性能开销,同时定义了代价函数,并且给出了状态转移矩阵;然后,通过平稳状态与网络可用性关系的分析,求解出平稳分布并作为QoS运行开销的动态权重,实现了以业务运行代价最小为特点的网络可用性评判。仿真结果表明,所提模型构建的遍历性转移矩阵存在平稳分布,对网络可用性评判是可行的。该模型能针对不同业务的QoS标准,且有效针对具体业务衡量网络的可用性。     

移动卫星通信中基于马尔可夫链的两状态信道模型研究

文章基于马尔可夫链提出两状态陆地移动卫星通信信道模型,该模型状态之间的转移被描述为马尔可夫(Markov)过程,且每状态内接收信号包络的概率密度函数服从不同参数集的Loo分布。同时对这一过程进行理论上的数学建模与仿真分析,得到包络的一阶、二阶统计特性,并将其与同样环境下的实测数据相应的统计特性进行对比。仿真结果表明,在多种环境下,基于马尔可夫(Markov)链的两状态陆地移动卫星通信信道模型的统计特性与实测数据的统计特性非常接近,这证明了所建立的信道模型能够模拟实际环境中的卫星移动通信信道,为以后移动通信技术的评估以及系统的规划搭建有效的平台,同时也具有很广泛的适用性。     

Distributed disk-based algorithms for model checking very large Markov chains

In this paper we present data structures and distributed algorithms for CSL model checking-based performance and dependability evaluation. We show that all the necessary computations are composed of series or sums of matrix-vector products. We discuss sparse storage structures for the required matrices and present efficient sequential and distributed disk-based algorithms for performing these matrix-vector products. We illustrate the effectivity of our approach in a number of case studies in which continuous-time Markov chains (generated in a distributed way from stochastic Petri net specifications) with several hundreds of millions of states are solved on a workstation cluster with 26 dual-processor nodes. We show details about the memory consumption, the solution times, and the speedup. The distributed message-passing algorithms have been implemented in a tool called PARSECS, that also takes care of the distributed Markov chain generation and that can also be used for distributed CTL model checking of Petri nets.     

Reachability problems for Markov chains

We consider the following decision problem: given a finite Markov chain with distinguished source and target states, and given a rational number r, does there exist an integer n such that the probability to reach the target from the source in n steps is r? This problem, which is not known to be decidable, lies at the heart of many model checking questions on Markov chains. We provide evidence of the hardness of the problem by giving a reduction from the Skolem Problem: a number-theoretic decision problem whose decidability has been open for many decades.     

Model checking conditional CSL for continuous-time Markov chains

In this paper, we consider the model-checking problem of continuous-time Markov chains (CTMCs) with respect to conditional logic. To the end, we extend Continuous Stochastic Logic introduced in Aziz et al. (2000) [1] to Conditional Continuous Stochastic Logic (CCSL) by introducing a conditional probabilistic operator. CCSL allows us to express a richer class of properties for CTMCs. Based on a parameterized product obtained from the CTMC and an automaton extracted from a given CCSL formula, we propose an approximate model checking algorithm and analyse its complexity.     

Model checking for action-based logics

A model checker is described that supports proving logical properties of concurrent systems. The logical properties can be described in different action-based logics (variants of Hennessy-Milner logic). The tools is based on the EMC model checker for the logic CTL. It therefore employs a set of translation functions from the considered logics to CTL, as well as a model translation function from labeled transition systems (models of the action-based logics) to Kripke structures (models for CTL). The obtained tool performs model checking in linear time complexity, and its correctness is guaranteed by the proof that the set of translation functions, coupled with the model translation function, preserves satisfiability of logical formulae.     

基于隐Markov以太工业控制网络实时性研究

基于以太网的工业控制网络是工业控制系统的发展趋势。本文系统分析了以太工业控制网络系统的时延机理和相关的解决办法并结合遗传算法提出了基于隐Markov模型以太工业控制网络系统的实时性解决方法。     

模型检测MESIF Cache一致性协议

在处理器从单核向多核演进的过程中,为了获得更好的性能和可扩展性,适用于多核处理器系统的Cache一致性协议变得越来越复杂。Cache一致性协议的验证一直是模型检测在工业界主要应用之一,被工业界和学术界关注。相对传统方法而言,微结构级的模型检测能够描述和验证更多的协议细节。利用NuSMV工具对Intel公司的MESIF Cache一致性协议进行模型检测在微结构层次上进行了建模,并对该协议进行模型检测,试验结果证明了此方法的有效性。     

基于频繁的Markov链预测模型

预取技术通过在用户浏览当前网页的时间内提前取回其将来最有可能请求的网页来减少实际感知的获取网页的时间.传统的Markov链模型是一种简单而有效的预测模型,但同时存在预测准确率偏低,存储复杂度偏高等缺点.通过提出一种算法来减小存储空间,最后通过证明能有效减小存储空间.     

Risk-sensitive probability for Markov chains

The probability distribution of a Markov chain is viewed as the information state of an additive optimization problem. This optimization problem is then generalized to a product form whose information state gives rise to a generalized notion of probability distribution for Markov chains. The evolution and the asymptotic behavior of this generalized or “risk-sensitive” probability distribution is studied in this paper and a conjecture is proposed regarding the asymptotic periodicity of risk-sensitive probability and proved in the two-dimensional case. The relation between a set of simultaneous non-linear and the set of periodic attractors is analyzed.     

Finite horizon analysis of Markov Chains with the Murϕ verifier

In this paper we present an explicit disk-based verification algorithm for Probabilistic Systems defining discrete time/finite state Markov Chains. Given a Markov Chain and an integer k (horizon), our algorithm checks whether the probability of reaching an error state in at most k steps is below a given threshold. We present an implementation of our algorithm within a suitable extension of the Murϕ verifier. We call the resulting probabilistic model checker FHP-Murϕ (Finite Horizon ProbabilisticMurϕ). We present experimental results comparing FHP-Murϕ with (a finite horizon subset of) PRISM, a state-of-the-art symbolic model checker for Markov Chains. Our experimental results show that FHP-Murϕ can handle systems that are out of reach for PRISM, namely those involving arithmetic operations on the state variables (e.g. hybrid systems). This research has been partially supported by MURST projects MEFISTO and SAHARA. This paper is a journal version of the conference paper [16].