双时间戳论文（精选7篇）
双时间戳论文 篇1
摘要：随着移动计算的广泛应用,数据同步技术在分布式环境下发挥越来越大的作用。针对分布式移动环境的特殊性,研究并提出一种基于双时间戳的数据增量同步机制,为移动数据库复制技术提供一种可行的解决方案。在保证数据一致性的同时,为系统层级扩展提供了新的思路。实验结果表明,设定合理的批量传输单位能有效地提升同步机制的可靠性。最后设计并实现移动执法智能终端系统,辅助现场作业。
关键词：数据同步,双时间戳,扩展,批量传输
0 引言
在移动互联网领域,网络环境变得越来越复杂。传统的在固定主机FH( Fixed Host) 保存数据副本,移动终端机MH( Mobile Host) 获取的数据都来自FH,数据流动是单向的集中式架构不适合当前的移动环境。根据Jim Gray等提出的两级复制机制思想,使用FM和MH都保存数据副本的两级分布式架构。两者是一对多的关系( 一个FM对应一个或多个MH) ,数据交流是双向的,并采用松散性的差异式同步策略[2]成为应对当前移动网络环境的主要选择。
同步粒度是移动数据库数据同步的基本单位,根据是否为事务性主要分为两类: 事务、元组。利用事务提交变更可以保证数据的ACID特性,但事务提交需要保持一段时间的连接性,回滚过多容易影响系统效率[3]。而当前主流的移动操作系统对远程事务支持不足,采用元组作为同步粒度是该类系统的一个考量。本文研究背景以移动环境下的作业为主,以元组作为同步粒度,提出基于双时间戳的数据增量同步机制,有效地保证数据一致性和可用性。
1 算法研究
分布式系统一般采用经典的主从式结构,体系架构如图所示。
这里,我们需要处理好所谓的“CAP原理”[4],即数据一致性( C) ,系统/数据可用性( A) ,分区容错性( P) 。而分区容错性是在分布式系统中必须实现的,因此为了保证系统/数据的可用性,需要提供在线或是离线时的数据存储,以及进一步通过会话在软实时的更新传播下实现数据的一致性。而当前的移动数据库系统同样可以视作一个准分布式体系结构[5]。
数据同步分为上传和下载两个部分。上传一般由MH发起; 下载则有不同的实现方式,可以由MH发起,也可以是在MH上传之后由FM端将针对MH的差异数据返回,即将上传下载合并。
针对数据冲突,由于时间上的异步而产生的冲突是不可避免的,只能在逻辑上牺牲一方的操作或者在应用上按一定策略进行操作内容的合并。主要机制包括: 主从表、逻辑合并、分组[7]。主从表机制虽然简化了冲突处理方式,但弱化了数据操作的时间顺序; 逻辑合并和分组机制则都需要根据相关业务设置策略。本文侧重数据操作的时间顺序性( 基于时间顺序法) ,该方法除了实现简便,还能方便在现有的集中式架构基础上扩展分布式系统。
增量同步,需要把整体任务细分成多个独立的子任务,本地通过队列维护多个子任务,并利用数据的时间戳记录同步的进度。而对于任务生成源的选择,文献[6]给出从FM端获取的方式,好处是方便于FM端对任务统一管理,缺点是增加了同步的请求次数成本。
本文的数据同步模型如图2 所示。
其中MH和FM各自包含冲突检测、冲突处理、结果处理的功能,以及MH端另外设置了任务的生成、管理功能,其中各个模块之间是调用的关系。
1. 1 同步算法
为了便于在现有的集中式系统上扩展分布式系统,本文在MH和FM数据库元组原有属性的基础上做以下调整:
MH端设置或添加三个属性,如表1 所示。
FM端设置或添加以下三个属性,如表2所示。
其中,本地变更时间记录MH操作时间,用于数据的同步冲突检测。服务器变更时间用于增量数据同步的参照,因此保证MH和FM时间的一致性显得尤为重要[8]。删除标记用于标记被删除的数据对象Ddel,删除标记的引入,将删除操作d( D) 当做是一个更新操作u( D) ,即d( D) ∈ R( x | x ∈ u( D) ) ,而且因为任何人都不会对已加删除标记的记录进行修改操作,所以删除有删除标记的记录不会引起数据库数据的删除冲突[9]。
针对TC和TS,通过设置以下几条基本操作规则,作为数据同步的标准:
( 1) MH对于数据对象D的操作,只涉及TCm。
( 2) 数据对象D的操作结果上传到FM时,令TCf= TCm,TSf= 服务器时间。
( 3) FM单独对数据对象D的操作,涉及TCf和TSf,且TCf= TSf= 服务器时间。
( 4) MH下载数据对象D ,令TSm= TSf。
( 5) 冲突处理以数据对象D的最晚TC为考量( 时间顺序法) 。
其中规则( 3) 表现为在FM端直接修改数据的情况,等同于是规则( 1) 和规则( 2) 的无间隙合并操作。数据同步围绕TCm、TSm、TCf、TSf进行,图3 给出了针对该4 个属性的时间顺序闭环图。
对于FM上的数据对象D ,TCf~ TSf称之为其操作op( D ) 的“风险时段”,即如果其他Site上有op( D ) ’的TCm处于该时段,则op( D ) 有在该时间段被替换的风险,否则予以保留。所以需要将上传下载分开,并且每次MH端要先执行下载操作,通过下载其他MH可能操作并上传过的数据对象,错开TCm和TCf~ TSf,可以降低本地操作被替换的几率。
对于数据的上传下载,设置单次数据传输大小上限N 。因为考虑到移动网络环境下数据上下行带宽的差异性以及本地设备硬件性能等问题,对于大量数据的传输,如果不分批次进行,一旦传输失败,则要全部重新开始,这无疑提高了操作的失败成本; 如果每个批次分得过小,又会增加网络请求次数成本。
数据上传算法描述如下:
数据下载时序一致性保证策略:
MH需要从FM获取数据集总量包含m个数据对象,对应的TSf依次为t1,t2,…,tm( t1≤ t2≤ … ≤ tm) 。假设分为多次获取,对应的时序分别为( t1,t2,…,ti) , ( tj,tj +1,…,tk) ,…,( tl,tl +1,…,tm) 。为了保证数据下载时序一致性以及避免重复下载的情况,需要保证相连的两序列满足ti -1≤ ti< tj≤ tj +1条件,因此对于i的设定尤为重要,在不考虑数据压缩的前提下,引入因子 η,令v = η × N/D,0 < η < 1,对于tv,利用时间序列前后探测率先满足tp< tv< tq条件的tp和tq。对于以下三种情况,采用在FM返回的数据中添加状态码flag( 1,2,3) 来区分: ( 1)如果( q - 1 - v) /( N/D) > 1 - η,则令i = p; ( 2) 如果( q - 1 - v) /( N/D) ≤ 1 - η,则令i = q - 1; ( 3) 对于数据局部密集( 即t1= t2= … = tv= tv +1= … = tq -1) 的情况,即当( q - 1 - v) /( N/D) > 1 - η 且p < 1 时,需要将tv时刻所有的数据分批次传输给MH。以上一批次MH的确认状态作为发送下一批次的参照,并在( 3) 情况下将FM返回的最后一批次数据的标记flag改为1 或2。
数据下载算法描述:
对于比较是否为相同对象,可以采用分值法: 根据关键度给若干属性设置不同的分值,针对两个元组相同的属性,累加分值,根据总分所属区间判定。采用分值法比较对象,可以解决数据添加冲突,但如果比较的属性过多容易影响效率,需要权衡把控。
1. 2 多级扩展
前面提到的TC-TS机制适用于两级分布式主从架构系统,有时因为一些其他需求,需要将FM当做MH,如各个部门的系统需要定时将新数据上交到中央数据库; 或是将MH当做FM,如外出作业的几个人员,因为业务需要,可将数据都传给其中的一个人,由他和FM交互数据,临时充当了FM的角色。针对三级或多级分布式主从架构系统,TC-TS理论上也可以很容易得到扩展,如图4 所示。
其中Level-1 与Level-2、Level-2 与Level-3 之间各自形成闭环,并通过TS2实现数据的跨层交互。TS2在不同的闭环中起着不同的作用。每层只负责跟相连层通信,降低了数据的耦合,体现了数据同步的层次性。
2 技术实现与应用
相比于传统的时间戳方式: 在元组中添加2 个属性,如创建时间和更新时间,通过它们获取新插入和更新过的数据; 本文采用本地时间结合服务器时间的形式,更加契合客户端和服务器的同步关联性,结合删除标记,降低了冲突检测的维度。
2. 1 Android平台下数据同步流程
通过后台设置任务队列并定时获取队列任务,根据任务标识执行相应的子任务。
部分代码如下:
下载的数据主要包括两类: ( 1) 表记录; ( 2) 数据库文件。对于记录,可以采用本文的增量同步机制更新; 对于数据库文件,通过从FM下载压缩包的形式更新,系统中往往定义有数据库的版本信息,因此可以和系统更新相结合。
初次安装系统,提示下载对应版本号的初始数据库; 每次升级系统,自定义的数据库升级方案可以将数据库版本号升级到最新; 如果选择替换本地数据库,要保证本地没有待上传的数据,以免数据丢失。
如果本地有数据待上传,则当用户退出系统时,提醒用户是否上传,退出后在后台上传数据,上传结束后通知用户上传结果。
2. 2 本地化编码策略
分布式环境下,因为某些特殊业务需要( 如本地新增数据的离线打印) ,可能需要在本地生成一些标识信息( 如标识记录的编码) ,我们通过在标识信息基础上添加后缀的形式,并通过语义控制,一定程度上保证了数据的有效和合理性。
该策略比较适用于网络信号差或没有信号的环境,虽然可能存在本地打印的标识信息和服务器端保存的标识信息相差一个后缀的情况。但对查询等操作影响不大,满足了一定程度上的业务需求。
2. 3 实验结果与分析
测试使用的是2G网络,基于Android2. 3. 3 系统,利用第三方类库Ksoap2 调用Web Service接口实现数据交互。以同步500 MB的数据为例,通过设置断网模拟偏远地区无信号时的环境,对于设定不同的N,实验结果如图5、图6 所示,其中横坐标表示N大小,单位MB。
实验结果表明,使用上述增量同步方法,能有效地保证数据同步的一致性,并且通过合理的设置N ,不仅可以缩短总的同步时间,也能有效降低同步请求被阻断的几率,提高了系统的可靠性和使用性。
3 结语
随着移动互联网的不断发展,移动办公在今后的作用会不断显现。本文通过设计的数据增量同步机制,以及其他一些策略的调整,便于在原有的集中式系统架构下扩展,并且也探讨了批次传输大小对同步性能的影响,保证并最大化满足人员的办公需求。基于本文设计并实现的移动执法智能终端系统,已经在农业执法领域投入使用,并取得了良好的成效。
参考文献
[1]陶涛.基于Android平台的嵌入式数据库同步及优化策略研究[D].天津:南开大学,2010.
[2]姚岚.基于Web服务的智能客户端数据同步[D].上海:复旦大学,2008.
[3]张晓丹,何锐,牛建伟.基于关联事务的移动数据库冲突处理算法[J].计算机工程,2008,34(16):60-65.
[4]Lomotey R K,Deters R.Reliable Consumption of Web Services in a Mobile-Cloud Ecosystem Using REST[C]//2013 IEEE Seventh International Symposium on Service-Oriented System Engineering(SOSE),2013(3):13-24.
[5]赵旸.基于移动数据库的事务处理模型的研究[J].计算机工程,2006,32(5):68-70.
[6]刘宇,戴鸿君,郭凤华,等.Android平台可增量同步的网络应用协议[J].计算机工程,2011,37(18):59-64.
[7]邵宝军,王延章.非连接数据库间的数据交换方法[J].计算机工程,2004,30(17):77-78.
[8]茅敏涛.基于Mobilink实现分布式数据库同步的研究[J].计算机应用与软件,2009,26(6):152-154,174.
[9]封明玉,赵政,张钢.分布式环境下数据冲突及其解决方案[J].计算机应用研究,2002,19(2):72-74.
一种改进的动态时间戳分析方法 篇2
随着信息技术的应用和普及, 把计算机和网络作为攻击目标的犯罪活动日益猖獗。与计算机相关的法庭案例如电子商务纠纷、网络入侵、计算机犯罪等也不断出现。一种新的证据—存在于计算机及相关外围设备包括网络介质中的电子证据逐渐成为新的诉讼证据之一。
计算机取证就是将计算机调查和分析技术应用于对潜在的、有法律效力的证据的确定与获取上。它从存储介质中提取数字形式的证据, 并将其用于刑事或民事诉讼的技术, 在对抗数字化犯罪中具有关键性作用。电子证据本身和取证过程的许多有别于传统物证和取证的特点, 对司法和计算机科学领域都提出了新的挑战。为了有效的解决这些计算机犯罪问题, 必须首先解决计算机证据的问题, 因此当前在我国开展计算机取证的研究具有重大意义。
1 动态时间戳分析方法及存在的问题
在计算机系统中, 文件的产生时间是根据计算机的系统时间而定的, 而计算机系统时间通常因人为的或者是物理的原因变得不准确, 所以确定文件产生的真实时间就显得非常重要。
在计算机取证过程中, 时间戳的功能就是把发生在数字领域的事件与发生在现实物理世界的事件关联起来, 建立因果联系。然而, 当一台计算机的时间和它所在地区的标准时间不同步时, 就无法将这台计算机上事件发生的时间与现实物理世界发生的事件的时间做关联分析。如果时间戳不准确, 会混淆两个事件发生的前后顺序。Boyd&Forster建议在取证过程中获取的以计算机的系统时间作标记的证据, Nolan则建议看它的系统时区设置是否和当地的时区相同。但是这些建议也只能纠正调查者在调查时看到的当时的系统时间的异常, 无法确定这之前的系统时间是否被改动过。
Weil提出了动态时间戳分析的方法, 在假设文件修改时间、访问时间、和创建时间相同的情况下, 将该文件的这三个时间与文件内容里包含的时间进行关联分析。该方法能够纠正系统的时间偏差, 获得系统事件产生的真实时间。
Weil在他的文章里列举了一个简单的例子, 来说明动态时间戳分析的具体过程。因为动态时间戳分析需要一个可靠的外部标准时间, 以这个标准时间为依据, 来校正文件的MAC时间。而NTP协议的应用使得Internet中的时间和标准时间能够同步, 所以Weil选择了Internet临时文件夹中保存的网页为研究对象进行分析, 在这些网页内容中搜索那些存在时间信息的网页, 将这个时间和网页的MAC时间对比, 校正M A C时间。一个实例如表1所示。
上面的列表中从左至右包含了文件目录、文件名、修改时间、访问时间、创建时间、在网页内容中获取的标准时间、时区设置以及标准时间和MAC时间的差值。从表中可以看出来, 因为Difference这列的时间差别比较小, 只有两分钟, 所以可以直接得出这里面某个网页产生的真实的时间范围。例如File1.html产生的时间范围就是12:00—12:02。Weil也提到了如果时间差值这列数据出现了较大的偏差, 那么不能直接计算, 而需要先用别的方法对数据进行处理, 但是没有给出具体方法。
2 改进方案
为了解决上述问题, 我们将异常检测算法引入动态时间戳分析方法中。
2.1 异常检测算法
异常是在数据集中与众不同的数据, 使人怀疑这些数据并非随机偏差, 而是产生于完全不同的机制。它的行为与正常的行为有显著的不同。国内外关于异常检测算法文献非常多, 这些方法大致分为四类:基于统计的方法、基于距离的方法、基于偏差的方法、基于密度的方法。
基于统计的异常检测应用主要局限于科研计算, 这主要是因为必须事先知道数据的分布特征, 这就限制了它的应用范围。因为序列异常在概念上仍然有一定缺陷, 遗漏了不少的异常数据, 所以序列异常检测算法并没有得到普遍的认同。基于距离的算法不需要用户拥有任何领域知识, 在概念上更加直观。基于密度的异常观点比基于距离的异常观点更贴近Hawkins的异常定义, 因此能够检测出基于距离异常算法所不能识别的一类异常数据——局部异常。局部异常观点摈弃了以前所有的异常定义中非此即彼的绝对异常观念, 更加符合现实生活中的应用。本文采用基于距离的异常检测算法。
2.2 异常检测算法在动态时间戳分析方法中的应用
假设计算机系统曾经有被故意的修改过系统时间, 那么这段时间内产生的文件, 它们的MAC时间就和标准时间相差很大, 这会导致要分析的文件集合中时间的差值出现较大的偏差。比如一部分时间的差值为两分钟左右, 而另一部分则为1天左右。这时就不能像上面那样分析。合理的方法是把差值为两分钟的那些文件作为一个子集, 把差值为1天的文件作为另一个子集, 这样就能精确的纠正出系统在不同时间段所产生的时间偏差, 然后计算得出准确的文件产生的时间范围。
异常检测用来检测一个集合中的异常点的情况, 利用基于距离的方法, 本文以文件的MAC时间和标准时间的差值组成待检测的集合, 然后对这个集合循环使用异常检测算法, 目的不是找出异常点, 而是要把这个集合分成几个合理的子集合, 然后再分别对子集中的时间差值作进一步分析。
首先要对待检测的数据进行捕获, 本文以Windows XP系统下IE6.0版本的Internet临时文件夹中的网页文件作分析对象, 假定系统的时间和由网页内容里获得的时间设置的时区一致, 都是所在地区的时区时间, 忽略了MAC时间或许不同的可能。由于对分析有作用的只是MAC时间, 由网页内容中获得的时间, 即标准时间, 还有两者的差值, 因此搜索时, 只把MAC时间和标准时间记录下来, 以供分析。进行数据捕获时, 只需首先定义某种或几种特定的时间格式, 然后再从网页的内容中搜寻和匹配具有这些格式的时间数据, 并且转为统一的一种时间格式;另外搜索到对应文件的创建时间, 一并存放到文本文档中, 形成时间列表。然后, 对文件的创建时间和标准时间作差, 最后将文件的创建时间、标准时间, 还有时间差值三个要素存放到文本文档中, 作为数据源, 进行异常检测。该算法需要输入的参数是所有时间差值的集合, 另外需要手工输入阈值è, 来控制检测出多少异常点, 最后把异常点集和非异常点集连同每个时间差值对应的文件创建时间和标准时间分别输出。算法如下:
(1) 定义这些时间差值为异常点xi, i=1, 2, …, n它们的值定义为f (xi) 。将所有的异常点的集合表示为S (x) ={xi|i=1, 2, …, n}。
(2) 计算均值, 及比较值hi=h (xi) =f (xi) -g (xi) 。
(3) 给定集合{h1, h2, …, hn}, 计算均值ì, 标准方差ó, 及。
(4) 使yq成为yi中最大的那个和设定的è阈值进行比较, 如果yq>è, 那么对应的xq就是异常点, 将该点移除, 再从余下yi中选择最大的和è比较, 直到没有比è大的为止。
(5) 如果没有移除点, 查看è选择是否合适, 不合适则重新选择, 回到第一步执行;否则结束。
(6) 将移除的点作为一个集合存放起来, 对未移除的点集, 重新选择合适的è值, 重复上述步骤。
2.3 文件真实时间范围的确定
用异常检测算法对差值集合进行分类之后, 每个子集的差值区别范围不是很大, 我们可以由此推测出文件产生的真实时间范围。每个子集里面, 差值有大有小。选择最大与最小的两个差值, 然后用每个文件产生的时间和这两个差值相加, 就得出了每个文件产生的真实时间范围。
对Internet临时文件夹中的网页文件进行分析, 经过程序运算, 结果如下:
不考虑M A C时间不同的可能性, 这里M A C时间指文件的修改时间, Observed指文件内容中获取的标准时间, Difference指时间的差值, “+”代表Observed大, “-”代表MAC大, real time range代表真实时间的范围, Threshold即是指è。当è值选择为2时, 提示没有移除点出现, 更改è值为1, 出现移除点, 即为“Threshold=1”下面的三条列表;然后分别选择值è为0.6, 0.3, 其分别对应的移除点为“Threshold=0.6”下面三条列表和“Threshold=0.3”下面三条列表。每三条列表就为一个子集, 针对每个子集的“real time range”结果如上, 提高了真实时间范围的精确性。
3 结束语
本文对动态时间戳分析方法进行了分析, 对于时间差值过大影响文件产生真实时间确定的问题, 提出一种改进的动态时间戳分析方法。该方法用动态时间戳算法分析文件的M A C时间和标准时间的关联关系, 对文件的M A C时间和标准时间的差值集合进行异常检测, 在差值之间出现较大的差距的时候, 能够把他们分成差距很小的几个子集, 再针对子集进行分析, 得出比较准确的文件产生的真实时间范围, 提高了分析结果的精确性。但是如果文件创建时间、修改时间、访问时间不一致时, 无法采用这种方法, 需要做进一步研究。
摘要：在计算机取证中涉及到取证事件因果关联分析时, 特定事件的产生时间是重点关注的因素。本文在分析动态时间戳方法的基础上, 提出一种利用异常检测方法确定文件产生真实时间范围的改进方案, 为计算机取证提供了有效依据。
关键词：计算机取证,时间戳分析,异常检测
参考文献
[1]Robbins.Judd.An Explanation of Computer Forensics.URL:http://www.computerforensics.net/forensics.htm.
[2]李炳龙, 王清贤.可信计算中的数字取证.武汉大学学报 (理工版) .2006.10.
[3]Stevens MW.Unification of relative time frames for digital forensics.D igital Investigation.2004.
[4]Boyd C, Forster P.Time and date issues in forensic computing a case study.Digital Investigation.2004.
一种基于时间戳的新闻推荐模型 篇3
互联网的普及使用户可以更方便地获取信息,但互联网中信息量爆炸式的增长,造成了严重的“信息过载”问题,用户很难从“信息海洋”中找到需求的信息。推荐系统作为一项重要的信息过滤技术,很早就被广大学者视为极具潜力的解决信息过载的有效手段而被广泛研究[1]。推荐系统根据用户以往行为在进行分析后对用户即将发生的行为进行预测。在商务领域,以亚马逊为代表的电子商务网站就是利用推荐系统增加商品销售的典型案例。推荐系统不仅能够为用户提供个性化的服务,而且能够与用户建立长期稳定的关系,提高用户忠诚度,防止用户流失[2]。
目前,个性化推荐系统分为基于内容的推荐系统、基于协同过滤的推荐系统、基于知识的推荐系统以及几种推荐系统的混合模型等[1,3,4]。由于以上几种算法各有所长,因此,很多推荐系统对上述算法进行组合以得到准确的推荐结果[5,6]。
另外,随时间变化,用户偏好会发生变化[7,8]。如果不及时更新用户偏好,使用已过时的用户偏好为其推荐信息或服务,将无法满足其个性化的需求,造成推荐系统性能的下降,客户的流失。针对该问题,研究人员将时间因素引入到推荐系统中以更新用户偏好,改善推荐系统的性能。郑先荣等人[9]为了及时捕捉用户偏好的变化,借鉴心理学中人的遗忘理论,引入了线性遗忘函数对用户评分进行加权计算。而邓娟等人[8]考虑到用户对项目的评分随时间迁移对当前用户偏好的影响会衰减,引进了按指数衰减的时间加权函数。相比于线性遗忘函数,按指数衰减的遗忘函数能更好地拟合用户偏好的衰减,因此印桂生等人[10]和张磊等人[11]分别提出了不同形式的按指数衰减的遗忘函数。在上述研究中,用户评分被看做用户偏好,因此可以直接进行相应计算,但在新闻推荐系统中,收集到的数据只有用户阅读过的新闻,并没有直接给出相应的评分,所以在新闻推荐系统中首先需要挖掘用户偏好。
针对上述问题,本文提出一种基于时间戳信息的新闻推荐模型。首先,使用分词工具对新闻标题以及新闻内容进行分词;然后,计算分词的相对词频,考虑到时间因素的影响,本文参考已有文献,引入了按指数衰减的时间加权函数;根据计算得到的相对词频,提出计算用户偏好的公式;根据计算得到的用户偏好,结合基于用户自身偏好和改进的协同过滤方法实现推荐;最后,使用真实数据验证本文提出模型的有效性。
1 提出的模型
本文提出的模型,首先根据新闻的分词计算用户对新闻主题的偏好,然后根据用户自身偏好和改进的协同过滤方法分别预测用户可能的偏好,最后对得到的用户偏好进行融合。在模型中本文引入时间戳信息来改善推荐系统的性能。
1)计算相对词频
在新闻推荐系统中,不能直接获取用户偏好,因此本文通过新闻分词来挖掘用户偏好。首先使用分词工具对新闻标题和新闻内容进行分词。由于随时间变化,用户偏好会发生迁移,原有偏好对当前用户偏好的影响比较小。因此,借鉴已有研究,采用按指数衰减的时间加权函数来调整分词对用户偏好的影响。时间加权函数[10]如下:
其中,t0表示当前的时间;ti表示用户阅读第i条新闻的时间,β为时间衰减参数。
用户阅读的新闻包括新闻标题和新闻内容两部分,但新闻标题的分词和新闻内容的分词对用户偏好的影响是不同的。新闻标题中的分词影响更大一些。因此,考虑到时间衰减的影响,本文提出了一种计算相对新闻分词词频的方法,其公式如下:
其中,N1表示第i个分词在用户阅读的新闻标题中出现的次数;N2表示第i个分词在用户阅读的新闻内容中出现的次数;N表示用户阅读的所有新闻标题和新闻内容的分词数量;tk表示第i个分词第k次出现的时间,α表示权重参数。
2)计算用户偏好
由于用户对新闻的偏好与阅读次数之间不是线性关系,而是随着阅读次数的增加,用户兴趣度增长速度逐步变慢,这符合著名的经济学理论———边际效应递减理论。即其他条件不变的情况下,如果一种投入要素连续地等量增加,那么产生的实际效应的增加速度会逐步下降。因此,本文根据边际效应递减理论使用式(3)来计算用户对新闻分词的偏好:
其中,a为对数的底数。当a的取值比较大时,得到的用户偏好的范围比较小,当a的取值比较小时,得到的用户偏好的范围比较大,本文中需要将用户偏好映射到[0,1]之间的数值,而fi∈[0,1],所以设定a=2。
在获取了用户对单个分词的偏好后,可以计算出用户对某个新闻标题的偏好,其计算公式如下:
其中,表示新闻标题中包含的分词的数量。
3)基于用户自身偏好进行推荐
由于用户偏好受自身因素的影响,例如用户的学历、兴趣等。因此可以根据用户的偏好来预测用户可能的偏好。预测步骤如下:
(1)根据目标用户最后阅读新闻的时间,选择近三天发布的新闻标题。
(2)根据计算得到的分词的偏好,根据式(4)计算用户对已选择出的新闻标题的偏好。
(3)对计算得到的新闻标题排序,选择出偏好最高的前5个新闻标题。
但是当给出的新闻标题中不包含用户已阅读过的分词时,根据式(3)预测的新闻标题的偏好会是0。因此,基于用户自身偏好的预测方法,不能发现用户对新的新闻主题的偏好。为了弥补基于用户自己偏好预测方法的缺点,本文还结合使用了改进的协同过滤方法。
4)基于改进的协同过滤进行推荐
(1)根据其他用户和目标用户浏览的新闻的共同的分词数量选择近似邻居。由于本数据集中用户阅读的新闻数量比较少,在寻找近似邻居时,不是以新闻标题作为一个项目,而是将单个分词作为一个项目。例如用户A和用户B,他们分别读了关于马航的5条新闻,但相同的新闻标题没有。这并不能说明A和B偏好不相似,因此,在寻找近似邻居时,使用单个的分词作为项目是合理的。
(2)在计算用户之间的相似度时,为了提高计算的准确性,本文考虑了用户之间共同分词数量对相似度的影响。假设用户A和B分词分别为100和200个,且共同的分词只有一个,计算得到的偏好相等,那么根据传统的相似度计算公式得到的相似度可能比较高,但显然,这是不合理的。因此本文使用改进的皮尔森相关系数来计算用户之间的相似度,其公式如下:
其中,Sc表示用户ui和uj阅读的新闻标题以及新闻内容的共同分词;表示用户ui对分词Sk的偏好;θ用户度量共同分词数量的影响,其计算公式如下:
其中,Wi表示用户i阅读的新闻标题的分词的集合。本文中设定只有当θ>0.2时,才计算用户偏好之间的相似度。表示用户ui对阅读过的所有新闻标题分词的平均值,其计算公式如下:
其中,表示用户ui阅读的新闻标题分词的集合。
(3)根据计算得到的相似度,选择前K个相似度最高的用户作为目标用户的近似邻居。
(4)由于新闻的特点,用户一般会阅读最近发生的新闻。因此,为了减少计算复杂度,本文根据目标用户最后阅读新闻的时间,从近似邻居最近阅读的新闻中选择出目标用户没有阅读过,且新闻的发布时间和目标用户最后阅读新闻的时间不超过三天的新闻标题进行预测。
(5)根据近似邻居的偏好预测目标用户的偏好。
其中,Un表示用户ui的近似邻居的集合;sk∈Ss,Ss表示选择出的符合要求的新闻标题的集合。
(6)对于新用户,本文根据其余用户的偏好以及新闻的发布时间,选择出最新的热门新闻推荐给新用户。
(7)对于新推出的新闻,一方面通过分词,来计算用户对该新闻的偏好,另一方面将该新闻推荐给时尚型用户。根据用户阅读新闻的时间与新闻发表的时间平均差来判断用户是否为时尚型用户,其计算公式如下:
其中,Nn表示用户ui阅读的新闻标题的数量,即Nn=|Sr|,Sr表示用户阅读的新闻标题的集合;表示新闻sk发表的时间,sk∈Sr;表示用户ui阅读新闻sk的时间戳。如果计算得到的平均时间差小于给定的阈值,则判定用户为时尚型用户。
(8)根据预测得到的偏好,选择偏好最高的前5个进行推荐。
5)推荐结果融合
由于基于用户自身偏好的推荐和基于协同过滤的推荐各有优缺点,因此,本文结合两种方法进行推荐。将基于用户自身偏好的推荐结果和基于协同过滤的推荐结果进行融合,选择出偏好最高的5个新闻标题推荐给目标用户。
2 实验验证和结果分析
1)数据集
使用爬虫工具从搜狐网站上爬取10 000个用户在1个星期内阅读新闻的行为信息。并对用户、新闻进行编号,另外还抓取了新闻发表的时间,以及用户阅读新闻的时间戳信息。经统计分析该数据集包含7156条新闻,每个用户阅读的新闻量如表1所示。
2)新闻标题及内容分词
本文使用分词工具———NLPIR汉语分词系统对新闻标题和新闻内容进行分词。但该系统不允许一次性对超过四句话的文本进行分词。为提升效率对该软件进行了改良。通过对文件编码进行替换来适配汉语字符特有的宽编码以及应用Windows核心编程API技术完成两个进程间的通信需求。制作出了一个全新的文本读写软件,将网上的分词系统内置其中,可以通过循环控制和进程间通信的手段一次性完成所有的分词工作。
3)评价标准
本文采用F值作为评价指标,F值不仅考虑了准确率,还考虑了召回率,可以更准确地度量推荐结果。其计算公式如下:
其中,P表示准确率,R表示召回率,它们的计算公式分别如下:
其中,Na表示推荐的结果是用户阅读的新闻,Nl表示所有推荐的新闻标题的数量。
其中,NT表示测试集中所有的新闻标题的数量。
4)结果分析
(1)参数α的影响
从图1可知,当α=1.3时,推荐结果最好。这是因为,当α=1时,即分词没有区分是新闻标题中的分词还是新闻内容中的分词,所以推荐结果的准确性低;1<α<1.3时,新闻标题中的分词所占比重逐渐增大,所以准确性提高;当α>1.3时,由于新闻标题中的分词所占比重过大,所以推荐的准确性开始降低。根据实验结果,在后续试验中,设定α=1.3。
(2)参数β的影响
从图2可知,当β=0.7时,得到的推荐结果最好。这是因为,当β取值比较小时,衰减速度比较慢,所以一些过时的偏好对现有偏好影响比较大,导致推荐结果的准确性降低;当β取值比较大时,用户偏好衰减速度过快,使一些偏好对现有偏好的影响降低,同样带来了推荐结果准确性的降低。综上分析,在后续实验中,设定β=0.7。
(3)不同推荐方法的比较。选择传统的协同过滤算法作为基准对比方法,即method1,本文提出的建模方法为method2,分别进行建模,对比推荐效果。实验结果如图3和图4所示。
根据图3和图4可知,当平均时间差阈值为1天时,获得结果最好,这是由新闻的实时性特点决定的。因此一般时尚型用户会在新闻发布的第一时间进行浏览。根据图3可知,与基于传统的协同过滤算法的推荐系统相比,本文提出的模型在F值最好的情况上提高了0.0322;根据图4可知,本文提出的建模方法,在建模时间上比基于传统的协同过滤的推荐系统缩短了23.39分钟。这是因为本文提出的建模方法不仅考虑了时间因素的影响,在使用协同过滤时考虑了用户共同偏好数量的影响,并且在建模过程中做了一些预处理操作。改进方法的预处理因为是一些统计计算,因此其计算复杂度比较小,而传统的方法需要计算目标用户和其他所有用户的相似度,所以计算的复杂度比较大。因此虽然改进方法增加了预处理操作,但总的计算复杂度却减小了。
3 结语
为了提高新闻推荐的准确性,本文将时间戳信息引入到新闻推荐模型中。首先,在计算用户对单个分词的偏好时,使用了时间加权函数来度量时间对用户偏好的影响;在为用户推荐新闻时,通过融合基于用户自身的偏好的推荐结果和利用改进的协同过滤算法推荐的结果来实现推荐。实验结果表明,本文提出的模型有效地提高了新闻推荐系统的准确性,并缩短了模型构建的响应时间。
摘要：互联网的高速发展,使用户很难在“信息海洋”中找到感兴趣的新闻,如何为用户准确推荐满足其需求的个性化新闻已成为当前研究的热点和难点。为了改善新闻推荐系统的准确性,将时间戳信息引入到新闻推荐模型中。首先,利用分词工具对新闻标题和新闻内容进行分词,并引进时间加权函数来计算用户对单个分词的偏好;预测用户偏好时不仅根据用户自身的偏好进行预测,还使用改进协同过滤方法来预测用户偏好;最后,通过融合得到的偏好值对新闻进行推荐。实验结果表明,该模型不仅能提高新闻推荐系统的准确性,还缩短了模型构建的响应时间。
关键词：时间戳,稀疏性,分词,新闻推荐
参考文献
[1]许海玲,吴潇,李晓东,等.互联网推荐系统比较研究[J].软件学报,2009,20(2):350-362.
[2]刘鲁,任晓丽.推荐系统研究进展及展望[J].信息系统学报,2008(1):82-90.
[3]刘建国,周涛,汪秉宏.个性化推荐系统的研究进展[J].自然科学进展,2009,19(1):1-15.
[4]王国霞,刘贺平.个性化推荐系统综述[J].计算机工程与应用,2012,48(7):70-80.
[5]乔向杰,张凌云.近十年国外旅游推荐系统的应用研究[J].旅游学刊,2014,29(8):117-127.
[6]李忠俊,周启海,帅青红.一种基于内容和协同过滤同构化整合的推荐系统模型[J].计算机科学,2009,36(12):142-145.
[7]柯良文,王靖.基于用户特征迁移的协同过滤推荐[J].计算机工程,2015,41(1):37-43.
[8]邓娟,陈西曲.基于用户兴趣变化的协同过滤推荐算法[J].武汉工业学院学报,2013,32(4):48-51.
[9]郑先荣,曹先彬.线性逐步遗忘协同过滤算法的研究[J].计算机工程,2007,33(6):72-73.
[10]印桂生,崔晓晖,马志强.遗忘曲线的协同过滤推荐模型[J].哈尔滨工程大学学报,2012,33(1):85-90.
双时间戳论文 篇4
时间戳(timestamp)是由国家认可的时间戳机构(TSA)颁发的电子凭证,能有效、客观、可靠地证明电子文件产生的准确时间及产生后内容的完整性,解决了电子文件与传统纸质文件具有同等法律效力的问题。通过为电子文件申请可信时间戳获得电子文件在产生时间、权属及内容完整性方面的具有法律效力的证据,达到"不可否认"或"抗抵赖"的目的。在实践中时间戳由我国法定时间机构负责保障时间的权威与准确,可信时间戳已经得到司法认可。2011年2月开始实施的GB/T 25064-2010《信息安全技术,公匙基础设施,电子签名格式规范》规定了电子签名五种格式类型:基本电子签名(BES)、带时间戳的电子签名(ES-T)、带完全验证数据的电子签名(ES-C)、带扩展的验证数据的电子签名(ES-X)、待归档时间戳的电子签名(ES-A)。ES-T是有着重要地位的一种电子签名,有着广泛的用途。
1 带时间戳的电子签名概述
1 1 带时间戳的电子签名形成
时间戳是一个经加密后形成的凭证文档,它包括三个部分:1)需加时间戳的文件的摘要(digest);2)时间戳机构DTS(digital time stamp service)收到文件的日期和时间;3)DTS的数字签名。一般来说,时间戳产生的过程为:用户首先将需要加时间戳的文件用Hash编码加密形成摘要,然后将该摘要发送到DTS,DTS在加入了收到文件摘要的日期和时间信息后再对该文件加密(数字签名),然后送回用户。书面签署文件的时间是由签署人自己写上的,而数字时间戳则不然,它是由认证单位DTS来加的,以DTS收到文件的时间为依据。ES-T中的时间戳所记录的时间应尽可能地接近BES的实际创建时间,以提供最大程度的安全保护,如果签名者没有提供ES-T,则验证者可以在收到电子签名时立即自行创建一个ES-T。
1 2 带时间戳的电子签名效力
随着互联网技术的发展,电子商务已经逐渐成为人们进行商务活动的新模式。越来越多的人通过网络进行交易,使得电子商务的发展前景十分诱人,而其安全问题也变得越来越突出,如何建立一个安全、便捷的电子商务应用环境,对信息提供足够的保护,已经成为商家和用户都十分关心的话题。ES-T是在基本电子签名(BES)基础上添加了时间戳,其目的是保证一定程度的长时间的有效性。当某些验证数据的安全性受到威胁时,数字签名上的时间戳或者一个安全的时间记录都可以帮助保护签名的有效性,只要这些安全威胁是在签名产生以后发生的。因为时间戳和安全时间记录可以有效证明一份电子签名是在这些安全威胁产生前创建的,所以这份电子签名就仍然可以保持其有效性。
1 3 带时间戳的电子签名作用
在用书面形式达成的合约中,文件落款签署的日期和文件签名都是合约十分重要的内容。合约上记载的时间即是合同成立的时间,也是期间计算的起点,关乎权利义务的履行。合约上的签名则是权利义务的承担者。不仅如此,文件落款签署的日期和文件签名还是防止文件被伪造和篡改的关键性内容。同样,在电子商务交易形成文件的过程中,时间也是十分重要的信息内容。时间戳是文件属性里的创建、修改、访问时间。数字时间戳技术是数字签名技术一种变种的应用。与纸质文件不同的是,电子签名中时间的形成有赖于数字时间戳服务者。数字时间戳服务是网上电子商务安全服务项目之一,能提供电子文件的日期和时间信息的安全保护。
2 对时间戳机构(TSA)的要求
可信时间戳必须由国家授时中心授权,由国家法定时间源来负责保障时间的授时和守时监测,任何机构包括时间戳中心自己不能对时间进行修改以保障时间的权威,只有这样产生的时间戳才具有法律效力。国家授时中心承担着我国标准时间的产生、保持和发播的任务,其授时系统是国家不可缺少的基础性工程和社会公益设施,是国家财政部专项经费支持的国家重大科学工程之一。为我国国民经济发展等诸多行业和部门提供可靠的高精度的授时服务,特别是为以国家的火箭、卫星发射为代表的航天技术领域提供时间服务。该中心相应地开展时间频率研究工作,紧紧围绕国民经济高速发展等对时频领域提出新的手段和更高精度的需求而开展,如在守时理论与方法、时间频率测量与控制、时间传递与同步、新的授时手段拓展、国际间远距离高精度时间传递与比对,时间尺度与频率标准、用户时间系统终端研制与开发等方面做了大量的基础与应用研究工作,取得了许多理论与技术成果,带动了我国在该领域的进步与发展,逐渐形成了具有自身优势和国际影响的时间频率研究、服务、发展中心。国家授时中心本身不是TSA,而是向TSA进行授时。
3 带时间戳电子签名在法律上的应用
可信时间戳符合我国《中华人民共和国电子签名法》、《中华人民共和国著作权法》、《合同法》等相关法律规定,是具有法律效力的电子凭证。《合同法》认为合同书、信件和数据电文(包括电报、电传、传真、电子数据交换和电子邮件)等可以有形地表现所载内容的形式都可以成为合同。采用数据电文形式订立合同,收件人指定特定系统接收数据电文的,该数据电文进入该特定系统的时间,视为到达时间;未指定特定系统的,该数据电文进入收件人的任何系统的首次时间,视为到达时间。作为我国信息化领域的第一部法律,《中华人民共和国电子签名法》的实施确立了数据电文的法律效力,规定了不得因其以电子形式存在而否认其证据效力
3 1 数字时代的版权问题
随着计算机、互联网技术的快速发展,越来越多的作品以数字化形式产生和传播,同时数字化作品的复制也变得极为便利:一篇文章、一首歌、一个电影、一个创意设计,几分钟、几秒钟就可以复制、传播,权属侵害、恶意抄袭广泛存在,严重影响了网站的健康发展,更侵害了权利人的合法权益。原创作品,凝聚着创作者心血,保护作品版权,是原创网站和创作者共同的心声。根据《中华人民共和国著作权法》作品产生即拥有著作权,一旦出现版权纠纷,规定了原创作者证明自己是作品权利人需要举证。因此,在创作完成后,作品公开发布前就为作品的创作时间、作品内容等保留足够且不可否认的证据极为重要,以便在证明作品归属或著作权产生纠纷的时候有效地保护自身的权益。作品版权保护是开展版权交易的基础,数字作品版权通过交易能产生巨大价值。数字作品产生快、数量多,需要适合数字作品特点的版权保护途径即快速、有效、简单、批量、低成本。针对数字化时代版权保护的新特点及需求,时间戳版权保护应运而生,时间戳能证明权利人在什么时间拥有一个什么样的电子文件(数字作品)。主要用在商业秘密保护、工作文档的责任认定、著作权保护、原创作品、软件代码、发明专利、学术论文、试验数据、电子单据等方面。及时申请时间戳,将拥有一个具有法律效力的权属证明。可以为广大原创网站、个人提供了一种权威、有效、先进的数字版权保护新方式。是保护交易双方利益的必要手段。
3 2 时间戳版权适用范围及保护特点
针对数字作品容易复制且取证难的特点,从数字作品创作开始就进行保护成为必要,时间戳是使用数字签名技术产生的数据,签名的对象包括了原始文件信息、签名参数、签名时间等信息。时间戳机构对此对象进行数字签名产生时间戳,以证明原始文件在签名时间之前已经存在。著作权人在创作过程中或发表作品之前登陆时间戳服务中心为作品申请时间戳,取得作品在时间、权属及内容完整性方面的一个具有法律效力的证明,保护自己的著作权。时间戳可以对各类数字格式作品进行保护,包括文字作品、口述作品、音乐(词曲)、剧本、戏曲等艺术作品,美术、建筑作品、摄影作品、电影作品和以类似摄制电影的方法创作的作品,工程设计图、产品设计图、地图、示意图等图形作品和模型作品、计算机软件、法律、行政法规规定的其他作品等。使用时间戳数字版权保护可以在作品创作过程中、完成后即时获得版权保护,24小时全天候取得作品权属证明,作品遭受侵权时,能拿出具有法律效力的证据,举证简单、有效、成本低,给企图侵权的人警示和威慑。而且,先进的时间戳版权保护不泄露原文件内容、批量保护数字作品、保护快捷(几分钟就可以完成数字版权保护)、时间戳机构可以24小时提供不间断版权保护服务,特别适合数字化时代的版权保护。
4 结论
市场信息瞬息万变,交易机会稍纵即逝,电子签名形成的时间在电子交易中十分重要。尤其是在对时间有着严格要求的领域更是如此,版权的取得,实用新型以及发明创造的新颖性无不对时间提出苛刻要求,这一切不仅要求缩短文件传输的在途时间,还要对文件的形成有明确的时间记录,以便将来有据可查。带时间戳的电子签名(ES-T)规范的不断完善和时间戳机构(TSA)服务能力的提升不仅加强了电子商务的安全,同时也大大提高了电子商务的效率。
参考文献
[1]张宁,熊光泽.引用计数与时间戳的混合垃圾搜集器算法[J].电子科技大学学报,2011(4):107-110.
[2]李峰,申利民,司亚利,等.一种基于实体上下文和时间戳的信任预测模型[J].电子与信息学2011(5):205-211.
[3]张飞,肖刚,程振波.基于时间戳服务的电子签章验证方法研究[J].浙江工业大学学报,2009(3):300-305.
双时间戳论文 篇5
1 时钟同步方式
时钟同步分为物理时钟同步和逻辑时钟同步, 物理时钟可分为内同步和外同步, 外同步是系统与系统外的物理时钟即UTC (Universal Coordinated Time) 同步, 内同步是实现系统内的时钟偏差不超过一定的范围。逻辑时钟同步是分布式系统内各主机之间的时间相差和不超过一定范围, 确保各个进程发生的事件在逻辑上一致。在分布式交互仿真网络中, 无需考虑各系统的物理时钟同步, 只要网络内部的所有节点时间之间误差不超过一定范围, 即逻辑时钟同步[3]。考虑到基于硬件 (GPS时钟源) 同步的代价高, 在时钟精度达到系统设计要求时, 采用软件同步方法[4]。在设计时钟同步模型时, 使用以下3个指标: (1) 稳定性, 系统能否长时间正常工作。客户方请求数量和频率一定时, 服务器能否给出精度相近的补偿值。 (2) 精度, 客户方获得时间补偿值的不确定范围。时间补偿值不确定范围越小, 精度越高。 (3) 工作效率, 为了获取特定的稳定性和精度, 系统消耗的CPU资源, 网络传输资源和其他资源。实验中选定分布式系统中的一个高性能服务器 (一般是仿真管理终端) 作为时钟同步服务器, 其他所有的客户端与服务器保持时钟同步。时钟服务器采用被动应答式服务建立单独的线程监听同步请求, 时钟同步服务器保留优先同上级或更高级别的时钟服务器进行时钟同步的功能。时钟服务器同上级时钟服务器的同步思想与本系统内的软件同步思想相似。各节点加入分布式网络时, 首先连续向时钟服务器发送带时间戳的同步请求信息Csi, 并记录每次发送信息时的时间值, 时钟服务器应答时, 同样记录收到请求信息时的本地时间值Tri和发送时的本地时间值Tsi, 将Tri和Tsi一起回传给客户端, 客户端接收到服务器的应答信息时, 记录当时的本地时间值Cri, 根据这4个数据, 计算出客户端的时钟误差δ, 和传输时延[5,6]。由于存在时钟频率的不稳定等问题, 要进行多次通信, 求均值, 减小时钟不稳定带来的误差。进行网内时钟同步时, 时间服务器被动应答, 减轻了时间服务器的工作量, 在大量仿真节点要求同步时, 可减少软件开销时间延时。服务器和客户端的时钟同步程序流程如图1所示。
2 时钟保持方式
由于各主机的时钟飘移, 再精确的时钟同步, 经过一段时间之后, 都会产生同步误差增大的问题, DR (Dead Reckoning) 算法和再进行网络同步的方法会带来增加网络通信量和占用CPU资源的问题。在分布式系统中, 各主机相对时间服务器的时间飘移近似成线性[3,4], 设客户端计时器上的时钟值为C, 时间服务器的时间为t, 分布式系统中的时钟存在如图2所示。在连续的同步请求中, 计算出一定时间内的时间误差λ, 根据系统对误差精度的要求, 客户端周期性进行调整。
3 分布式系统的时钟同步与保持算法描述
通过设计算法, 求出客户端的时间调整参数, 补偿时钟频率飘移带来的影响, 达到客户端时钟的同步与保持[7]。在Windows系统中, 可用windows API函授获取时钟信息, GetCurrentTime (·) 函授用于获取系统当前的时间。具体同步调整过程如下:
(1) 设定时钟同步精度γ。
(2) 发送同步时间戳, 并记录本地时间Cs1, 将Cs1放入数组Ps [·]中, 如图3所示。
(3) 时钟服务器端收到时间戳时, 记录收到时的本地时间Tr1, 放入数组Qr[·]中, 发送应答时间戳并记录发送时的本地时间Ts1, 将Ts1放入数组Qs[·]中, 将Tri和Ts1一起发送给客户端。
(4) 客户端收到应答时间戳时, 记录本地时间Cr1, 并将Cr1放入数组Qr[·]中。
(5) 当接收时间服务器的应答次数i<N (N为程序设定的同步请求时间戳有效次数) , i+1, 返回步骤 (2) , 当i=N时, 客户端停止发送时间戳。
(6) 计算网络平均传输时延θ, 在第1次通信中, 其发送时延θs为
θs=Tr1-Cs1 (1)
其接收时延θr为
θr=Cr1-Ts1 (2)
由于阻塞, 交换机的处理开销等, 每次同步请求的发送时延θs和接收时延θr是不同的, 发送和接收的时延也是分别不完全相同的, 但在概率平均上, 差别不大, 可以近似相等[8], 即
θr=θs (3)
则其平均传输时延为
(7) 计算客户端时间误差δ, 在第1次时钟同步请求时, 设其客户端的时钟比服务器端慢δ1, 则
则其平均时间误差δ为
(8) 计算由客户端计算机时钟飘移带来的误差λ, 假设客户端晶体频率变慢, 导致时间变慢, 则在一个同步过程中
λ= (Tsn-Tr1) -[ (Crn-Cs1) -2θ] (7)
在实际中, 计算机的晶震频率以一定的值偏快或慢, 由设定的精度可得, 客户端的时间调整周期为
(9) 调整客户端时钟。将客户端时钟值增加δ, 之后, 以
4 结束语
相对于其他同步方法, 文中方法在实现上更灵活, 各时钟客户端根据自身时钟频率的情况自主调整, 减轻了时间服务器 (仿真控制端) 的负担, 减少了网络的通信量, 在现有的算法中, 达到了时钟同步软件设计的3个指标要求。以上时钟同步程序体系设计及算法思想应用于某分布式仿真系统, 时钟同步精度达到了ms级且能较长时间保持, 符合目标速度为亚音速的仿真系统。
摘要：为解决分布式系统中时钟同步问题, 提出了时钟服务器被动应答式的同步结构、基于连续时间戳统计平均值的误差、时延计算方法和基于设定时钟精度的时钟保持技术。在软件同步的情况下, 提高了同步精度, 减少了因时钟同步而产生的网络通信量、各分布式系统的CPU开销。
关键词：时钟同步,时钟保持,连续时间戳,分布式系统
参考文献
[1]陈磊, 王海丽, 周伯昭, 等.导弹攻防对抗仿真的时空一致性[J].系统仿真学报, 2001, 13 (5) :87-89.
[2]郭齐胜, 张伟, 杨立功, 等.分布式交互仿真及其军事应用[M].北京:国防工业出版社, 2003.
[3]Andrew S Tanenbaum, Maarten Van Steen Distibuted.分布式系统:原理与范型[M].北京:清华大学出版社, 2008.
[4]王刚, 黄飞, 乔纯捷, 等.分布式网络时钟同步研究[J].仪器仪表学报, 2008, 29 (11) :2399-2403.
[5]宁伟, 张波, 王树梅, 等.基于分布式系统实现时钟同步的统计平均算法[J].计算机工程, 2005, 31 (5) :47-50.
[6]王晓冬, 张志武.以太网的时钟同步技术[J].电子工程师, 2008, 34 (9) :47-50.
[7]赵斌, 贺鹏.网络时间同步算法中时钟精度优化设计与实现[J].三峡大学学报:自然科学版, 2008, 30 (2) :74-75.
双时间戳论文 篇6
随着Internet的发展, 电子商务已经逐渐成为人们进行商务活动的新模式。越来越多的人通过Internet进行商务活动, 其所引发的安全问题将越来越受到重视。本文首先介绍电子支票安全支付模型系统的支付流程, 并对系统进行安全性分析, 接着介绍了数字时间戳工作原理, 工作方式及其基本问题。并对原系统重新进行安全性分析, 深入论证了时间戳技术在支付过程中抵御“抵赖”和重放攻击等攻击手段的重要作用。
1 电子支票安全支付系统支付流程
本文所研究的模型是基于Internet的电子支票安全支付系统。该模型由四部分组成, 要求四方能够模拟电子支票在网络上的安全支付, 支付流程图如图1所示。
1.1 模型的流程及技术应用的简单描述
(1) 客户生成电子支票, 具体实现为生成一个文本。文本的表项有金额, 申请人名称等。
(2) 客户将生成的支票文本数据用md5函数进行散列。得到的散列值用自己的私钥加密, 得到加密结果S1。再将明文文本使用AES技术用一个随机的密钥K进行加密, 得到密文S2。最后用银行的公钥加密这个密钥K, 得到S3。
(3) 客户将S1, S2, S3发送给银行A, 银行A用自己的私钥解密S3, 得到会话密钥K。然后用K解密S2 , 得到支票文本。利用md5散列文本, 得到散列值m1。用客户的公钥解密S1, 得到摘要m2。对比m1和m2, 如果一致, 就可以确认客户的身份。
(4) 确认客户的身份后, 银行A检查客户帐上是否有足够的金额进行支付。如果有, 则对用户的这张支票进行签名, 将签名后的数据付在支票文本上。此时, 支票开始起效。银行A将有效支票用密钥K’进行加密, 然后用客户的公钥对K’加密, 发送给客户。
(5) 客户将银行A发送回的支票用同样的方法加密支付给商家。
(6) 商家收到客户支付的电子支票后, 先确认是否为有效电子支票, 也就是是否有银行A的签名。如果为有效电子支票, 则商家将该电子支票加密后交给拥有自己帐户的银行B。
(7) 银行B持该电子支票和银行A进行相关交易。银行A收回该支票, 把客户帐上的相应金额划入商家的帐户。交易完成后, 给客户和商家发送通知。
此时, 一次电子支票的支付就完成了。
该设计中用到的安全方面的技术为:MD5散列函数生成数字摘要, RSA进行数字签名, AES加密会话密钥。但是只是能够简单模拟, 整个流程对网络本身的安全保证要求非常高。在“安全的金融专属网络中”和网下颁受数字证书这两个条件下, 此系统经论证是安全的, 三方中的任何一方都无法假冒或者篡改。
但假设客户端的支票被他人截获后去支付别的商品, 并反复使用, 或商家不承认拿到客户端的支票却要求多次发送以进行多次支付, 这样支付系统就无法抵御这种攻击。这是个未解决的问题, 因为该设计假设除了商家, 客户和银行外没有第四方存在。并且是个只有三个端的网络, 即使商家抵赖曾经收到过支票, 客户可向银行声明之前的支票作废。但如果把这个系统放在开放的网络中, 将有非常大的漏洞以至于是不能使用的。本文通过PKI等理论的研究提出了一种解决上面提及问题的方法。
1.2 Internet环境下的系统安全性分析
所有在网络上传送的数据都是经过两次处理的, 第一次使用会话密钥进行加密, 第二次使用接受方的公钥对这个会话密钥进行加密。这个过程在开放的Internet上不会有安全问题。因为即使数据被截获, 侵入者也没有解密密钥, 无法使用该支票。整个过程中, 发生四次有效支票的传送。第一次为银行A传回客户的有效支票, 第二次为客户向商家支付有效支票, 第三次为商家向银行B传送支票, 第四次为银行B将支票交易给银行A。若侵入者在任何一次传送时将支票截获, 然后用于支付给别的商家, 则他的支付对象会由于不能解密该支票进行校验而拒绝交易。侵入者也无法冒充银行的客户而开出其他客户的支票, 他没有那些授权客户的私钥, 银行会因无法确认他的合法用户身份而拒绝签字。如果侵入者截获数据并且篡改, 接受方会通过文本摘要立即觉察, 或因不能正确解密而察觉, 从而作废这张电子支票。侵入者或许会截获数据并将其丢弃, 那么客户只要作废原有的支票, 重新申请即可。在原有的网络上, 上述问题更不会存在。银行间的交易一般都在安全性相对较高的专有网络上, 如果需要重新申请也不会发生在交易的后期, 不会太过麻烦。
但是, 如果商家抵赖收到过电子支票, 却将其备份在自己的电脑里, 以备日后之需, 然后向客户索取另外一张支票;或者, 客户并没有支付电子支票却声称已经发送了电子支票, 责任在于商家没有收到, 这样, 在Internet环境下的安全性就出现了问题。
在本设计中, 网络里只有商家和客户, 银行作为中立机构不存在抵赖的问题。只要银行给客户开出的每张支票列个编号, 当商家说没有收到时, 客户向银行声明作废这张支票。这样即使商家日后需要, 这张支票也已经无法支付了。而商家确实没有收到支票的情况下, 是规定客户重发支票直到商家收到为止, 因为相同编号的支票, 银行只支付一次。这样问题就可以解决。然而在开放的网络上, 此法无疑是对银行的巨大挑战, 银行需要花大量的存储空间来管理客户的支票, 不管作废的或者使用过的或是正在等待兑现的支票, 都需要有备份, 这基本是不可能实现的。那么就应该用新的技术来解决这一问题。
2 时间戳技术研究
时间戳是近几年广泛运用的技术, 它能解决此系统在Internet环境下的安全性问题。
2.1 数字时间戳概况
时间戳为某个特定的时刻, 为某些信息的存在提供证据。要实现数字时间戳服务, 首先必需设置一台主机, 这台主机必需有权威认证的时间源, 它就是时间戳权威 (TSA-time stamp authority) 。TSA提供时间戳服务时, 首先接收来自客户端的任意数据, 然后计算这些数据与当前时间的信息摘要, 并对得到的消息进行签名, 然后签名被返回给客户端。通常, 客户端会发送一个需要时间戳的杂凑 (hash) 结果 (从数据获取消息摘要的过程称为杂凑) , 不需要为了得到时间戳服务而发送整个文件。数字时间戳服务的基本工作方式如图2所示:
数据文件所加的时间戳与存储物理媒体没有任何的关系, 即时间戳与物力媒体的独立性;充分地保证文件的完整性:时间戳的加入过程不应该改变数据。“完整性服务可防止数据未经授权或意外改动, 包括数据插入, 删除数据和修改等”;不可否认性:一旦时间戳由第三方生成并提交成功之后, 任何试图改变时间戳的行为都是非法的, 不被允许的, 也是容易轻易地被发觉的。针对这些问题, 下面将从Hash算法、可信时间源和密钥存储方式等方面进行分析。
(1) Hash函数
客户上传的文档信息和服务器返回给用户的签名时间戳信息都主要由 Hash 码构成, 下面来讨论Hash算法, 安全性及在完整性鉴别方面的应用。Hash函数是将任意长的消息映射为定长的Hash值的公开函数。该Hash函数可作为认证码。它的输入是不定长的消息M, 输出是定长的Hash码H (M) 。H (M) 不是密钥, 仅仅是输入消息的函数。Hash码是所有消息位的函数, 具有错误检测能力, 即改变消息的任何一位或多位, 都会导致Hash码的改变。Hash码在数字签名和认证中的基本应用可用下面一组符号表示:
A→B:M‖E[H (M) ]
即消息发送方A计算消息M的Hash码H (M) 并将其用密钥K加密, 然后连同M一起发送给接收方B。B将接收到的信息进行分解, 根据M计算其Hash码并与解密后得到的H (M) 进行比较, 以验证消息M是否被篡改过。
(2) 可信时间源
时间戳的基础是一个精确可信的时间源, 可以采用国家授时中心 (NTSC) 的NTP时间服务器和高精度时钟接口板提供时间同步服务, NTSC自己研制的PCI时钟接口板以国家授时中心标准时间uTC (NTSC) 的1PPS秒信号作为标准输入信号, 以GPS时间信号作为参考。对此二者作比较, 当两者之间的偏差小于5ms时, 以时钟板时间为准, 否则停止调整计算机时间。通过这种时间戳服务器时间的解决方案, 可提供好于10ms的对时精度。
(3) 密钥存储方式
使用Bouncy Castle的Keystore存储密钥, 它提供了基于口令的加密 (PBE-Password-Based Encryption) 方式保护密钥。 口令加密是杂凑加密和普通对称加密的组合, 口令由信息摘要算法 (如SHA-1) 进行杂凑, 结果为算法 (如Blofish) 构造一个数组密钥。
2.2 时间戳服务工作原理及流程
在《公钥基础设施 (PKI) 实现和管理电子安全》中是这样描述的:“时间戳协议 (TSP) 通过时间戳机构 (TSA) 的服务来提供数据在特定时间存在的证据。PKIX工作组当前正在对TSP进行研发。TSP是简单的请求/响应协议。PKIX工作对TSA强加了许多要求。可简单提炼为:时间戳也是一种安全服务, 可信的第三方时间戳权威 (TSA) 签名某信息, 为此信息在特定的时间前存在提供证据。
“数字签名+时间戳可提供不可否认服务”, 这就是时间戳在该设计中的价值所在。它的工作流程如图3所示。
3 运用数字时间戳的支付系统的安全性分析
3.1 防御“抵赖”
将时间戳服务器放在图4的位置, 就能够有效抵御“抵赖”这种系统攻击行为。
考虑商家的抵赖行为, 解决方法是让客户多增加一个步骤:银行A将有效电子支票发送给客户后, 客户在支付给商家前, 给支票加个时间戳, 并且规定该支票的有效时间, 假定是一天, 而时间的起始值就是时间戳标志的时间, 过了一天的期限, 该支票将不再具有兑换现金的功能。将加有时间戳的支票支付给商家, 如果商家抵赖, 则客户可以在过了这张支票的兑现时间后, 再向商家支付另一张支票。而银行A也可以将过期的支票作废删除。这样就不会产生对存储空间的压力, 商家也无法私藏支票了。问题是, 银行A如何知道客户的电子支票何时过期。提供时间戳服务的服务器可以提供公示服务, 即将使用了时间戳服务的数据项目公示出来, 这样银行A所要做的, 就是定时去公示上查阅支票的有效期。这样, 商家即使抵赖, 私藏, 也毫无意义, 他留下的将是一堆无法兑现的“空头支票”。
再考虑客户的问题, 如果客户没有发送支票, 却声称发送了支票, 虽然可以让其在以后周期地发送直到商家收到, 但这是个漏洞, 客户可利用这个规则, 无限制地拖延付款日期, 借口是:我发送了, 可惜你没收到。这就需要采取措施杜绝这种现象的发生, 方法就是寻找一个可值得信赖的第三方, 让客户将支票转交到第三方, 第三方再转发给商家。在这种问题上, 如果不能绝对信任客户的商业道德, 除了寻找“目击证人”外, 没有更好的办法。
3.2 防御重放攻击
考虑商家或者侵入者在支票有效期内重复使用的问题, 上文已分析过, 侵入者因为无法在短时间内解密在网络中始终处于加密状态的数据, 所以无法假冒处于交易中的任何一方使用电子支票的, 那么如果有重复使用电子支票的现象出现, 就是商家所为, 因为客户开出的支票只在银行A。解决该问题的方法是:规定银行对于拥有相同时间戳的、记录在案、等待兑现的支票只支付一次, 商家就无法实现重复使用同一张支票进行支付的攻击。
3.3 防范其他可能攻击
若侵入者欺骗客户, 假冒商家的公钥, 从而使之后的交易在客户和侵入者中进行, 则应通过其他方式解决, 譬如面对面地交换双方的公钥。电子支票交易适合大金额的贸易行为 (不适合小额交易和微交易) , 处于谨慎考虑, 不应轻易相信对方网上所声称的身份。商洽一开始, 就该“真实确认”身份, 包括确认对方的数字证书信息, 以得到真实有效的公钥。
4 结束语
本文分析了电子支票支付系统的基本流程、所用技术及在Internet环境下存在的安全问题, 提出了运用“时间戳”解决电子支票传输过程中防御“抵赖”以及重放攻击等问题的方法。并论证了加入时间戳以后的系统在Internet环境下的安全性。
可以认为:运用“时间戳”, 系统能够更加安全地简单模拟PKI的工作原则。但不能说它毫无问题, PKI技术目前虽已日趋完善, 即使它的技术处理和细节考虑都比此设计严密周全, 但必须要认识到PKI仍不完美, 它还存在很多的问题, 包括现在没有发现而将来可能凸现的问题。在实际生活中, 要考虑到的方面远远超过这个设计。安全程度和所花的代价之间永远需要一个权衡, 没有绝对的安全。
摘要：随着近年来电子商务的迅速发展, 在商家对商家 (B2B) 的电子商务中, 由于资金数额较大, 故电子支票支付的安全措施不能有任何疏漏。基于PKI技术中时间戳的工作原理, 针对电子支票支付模型在安全性上没有解决的问题深入研究, 着重阐述和分析了在利用了时间戳技术前后该模型系统的安全性, 同时对时间戳技术进行了介绍并加以论证。
关键词：时间戳,电子支票,PKI,B2B
参考文献
[1][美]Andrew Nash.公钥基础设施 (PKI) 实现和管理电子安全[M].清华大学出版社, 2002.
[2]何德全.PKI原理与技术[M].清华大学出版社, 2004.
[3]柯新生.网络支付与结算[M].电子工业出版社, 2004.
[4]肖德勤.电子商务安全保密技术与应用[M].华南理工大学出版社, 2005.
[5]钟鸣, 等译.电子商务安全基础[M].人民邮电出版社, 2001.
双时间戳论文 篇7
5月8日, 辽宁省档案学会在省档案馆新馆组织“时间戳技术在电子档案管理中的应用”研讨会, 省档案局 (馆) 副局 (馆) 长、省档案学会理事长许桂清参加会议并讲话, 档案学会、科研处、电子档案管理处、备份中心20余名同志参加了会议。
会上, 首先由北京联合信任技术服务有限公司董事长张昌利做了“联合信任时间戳技术在档案的应用”知识讲座。张昌利介绍了我国可信时间戳服务体系及技术原理, 可信时间戳在电子档案管理中的作用, 可信时间戳应用场景、策略、节点、申请程序及案例, 并对与会同志有针对性提出的时间戳技术问题, 进行了详细解答。参会同志对“联合信任时间戳技术在档案的应用”进行了广泛的讨论。最后, 许桂清副局 (馆) 长做了总结讲话。她要求大家要努力学习, 丰富理论、提高业务素质, 增强对新技术应用的自信, 尽快适应档案馆新的工作环境, 力争各项工作再上新台阶。
通过此次研讨, 大家感觉受益匪浅, 开阔了视野, 学习了新观念, 对时间戳技术在电子档案管理中的作用有了更深入的认识和了解。研讨会气氛活跃, 对提高全省档案管理信息化水平、创新思维以及解决数字档案馆建设中遇到问题, 将起到积极的促进作用。