V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lococo
V2EX  ›  程序员

论文要挂了!天啊!求指导!!!

  •  
  •   lococo · 2014-03-25 23:35:11 +08:00 · 3515 次点击
    这是一个创建于 3656 天前的主题,其中的信息可能已经有所发展或是发生改变。
    请君听我细细道来:

    [背景]
    现在有两个Table,一个是data tabel 一个是audit table
    data table中装有很多有用的数据,而audit table负责对data table的完整性进行校验

    现在假设audit table是不完全安全的(即可以保证有个别数据未被篡改)
    那么现在有个hash chain的办法去验证data table中数据的完整性,如下所示

    data table audit table
    row1 hash(row1)
    row2 hash(row2 + hash(row1))
    row3 hash(row3 + hash(ROW2)) //这里用hash(ROW2)代表上一行的hash值
    ···
    rowN hash(rowN + hash(ROWN-1))//这里用hash(ROWN-1)代表上一行的hash值

    也就是说我们只用确保最后一个hash值是安全的(没有被篡改)那么整个hash chain基本就可以判断是安全的

    验证的时候,我们只需要一条一条的做比对,则能检验出 data table中数据的完整性

    [问题]
    当data table中的数据太多的时候,一条条的比对的效率太低,是否有什么更好的方法使得数据完整性的检验效率能够提高?

    [想法]
    其实考虑了这么久,整个问题的核心就在于 [如何在确保安全性的同时减少IO次数]

    首先,data table里的数据是肯定要遍历的,所以这里的IO没办法做手脚,
    那么注意力自然而然就会转移到audit table那里

    最容易想到的其实就是 hash(row1+row2+···+rowi)这样可以减小audit table的访问次数,但这样io次数无非是从3N次减小到了 N/i 次。
    而且如果就这样就解决了,那毕业论文实在太扯淡了 ···

    所以到现在来说都没有什么突破性的想法实在捉急
    12 条回复    1970-01-01 08:00:00 +08:00
    ibillxia
        1
    ibillxia  
       2014-03-26 08:43:27 +08:00
    现在离毕业还早吧,lz不用太捉急,我当年因为考研,这个时候还没开始做毕设呢,到4月初才开始做的
    lz可以找指导老师交流交流,导师出这个题目心里应该有底的吧
    另外,lz可以在google scholar搜搜相关的论文,lz现在的想法是很简单,但其中肯定还有很多问题值得去思考和研究的~
    FatGhosta
        2
    FatGhosta  
       2014-03-26 12:56:35 +08:00
    你这个思维有点儿像git的提交树的思维啊
    lococo
        3
    lococo  
    OP
       2014-03-26 14:57:51 +08:00
    @FatGhosta
    哈?git提交树的思维是什么思维呀?刚刚去google上查了下没查到,你能稍微讲一下么?
    lococo
        4
    lococo  
    OP
       2014-03-26 14:59:27 +08:00
    @ibillxia
    之前也在scholar上面去找过,英文的看的好累好累,看完之后也没什么结果,中文的都感觉是一些很传统的验证方法,累感不爱 ,现在我没什么想法都不敢去找导师,好伤心啊
    FatGhosta
        5
    FatGhosta  
       2014-03-26 15:54:29 +08:00
    @lococo
    也许是我提交树这个词说得不对。。。咳咳
    git的每一次提交都会用SHA1哈希出来一个值嘛,第n次提交的值,跟第n-1次的提交的SHA1和这次的内容生成的第n次提交的SHA1值。
    Actrace
        6
    Actrace  
       2014-03-26 19:08:33 +08:00
    直接针对整个表进行hash.
    lococo
        7
    lococo  
    OP
       2014-03-26 19:37:54 +08:00
    @Actrace
    这样的话如果表一更新,这个hash值就需要更新,
    而且对整个表做hash需要把所有表中的所有数据提取一遍,
    所以,如果表会经常更新的话这个方法就不可取呀
    Actrace
        8
    Actrace  
       2014-03-26 19:40:10 +08:00
    你要解决的问题是安全性.
    hhkbp2
        9
    hhkbp2  
       2014-03-26 20:51:04 +08:00
    lococo
        10
    lococo  
    OP
       2014-03-27 00:46:06 +08:00
    @hhkbp2
    merkle tree很早之前就有人跟我提过 ·· 但是感觉对我的帮助不是很大
    merkle tree其实解决的瓶颈是网络传输,让网络传输的数据量减小
    而我要解决的瓶颈是减小单台机器上的IO次数

    虽然这么说,我一直其实也在想往merkle tree那边去做什么手脚
    或者如果有可以解决其他问题的话,可以改改论文的研究方向 ··
    当然我只是这么想想,但是没有实际的目标,也不知道有什么具体可行的办法
    lococo
        11
    lococo  
    OP
       2014-03-27 00:46:46 +08:00
    @Actrace
    什么意思?本身的hash chain 提供的安全性就已经很高了呀
    Actrace
        12
    Actrace  
       2014-03-27 08:46:04 +08:00
    我的意思是压缩文件校验的策略.
    @lococo
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5895 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 02:31 · PVG 10:31 · LAX 19:31 · JFK 22:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.