论文部分内容阅读
DNA计算的概念由Adleman博士于1994年首先提出,同：时第一次成功使用DNA计算方法解决了7个节点的汉密尔顿路径问题。此后,多种DNA计算模型被提出并用来解决不同的NP完全问题,DNA计算在解决NP完全问题时发挥了其海量存储和强大的并行计算能力,因此成为NP完全问题和其他困难问题的重要解决方法之一。在访问控制领域中存在大量的NP完全问题,这些问题的解决对访问控制领域的发展起了关键性作用,如何更好的解决这些问题是访问控制领域目前关注的重点之一,而DNA计算的海量并行计算能力成为访问控制领域中NP完全问题的潜在解决方案。基于角色的访问控制系统是一种将权限与角色相关联的访问控制机制,用户通过扮演角色来获得相应的权限。那么如何在保证用户权限范围不变的情况下,选取一个合适的访问控制策略配置方案,是访问控制研究的主要问题。本文研究了DNA计算在基于角色的访问控制系统中的应用,针对UAQ问题和混杂角色层次关系中的权限查询问题提出了新的DNA计算算法,并从理论上证明了算法的可行性。本文首先设计了UAQ问题的DNA算法,算法将UAQ问题中的角色和权限使用DNA链来描述,建立角色解空间并使用基本的生物操作来实现。UAQ问题的求解过程包括：权限初始化、无效角色移除和角色空间生成。其次设计了混杂角色层次关系中权限查询的DNA计算算法,算法通过求解最小唯一集(MUS)找出最小唯一权限集合,从而最终达到利用DNA计算解决混杂角色层次关系中权限查询问题的目的。本文所提出的两种算法生物操作时间复杂度均为问题输入长度的多项式。本文的结论表明,DNA计算技术可以在理论上解决访问控制领域中的NP完全问题,只要未来关于DNA计算的生物技术走向成熟,DNA计算技术可以对访问控制领域的发展起到推动作用。而本文的另一个更重要意义在于进一步充分证实了分子计算在完成复杂难解的数学运算的巨大潜力。