SpanDex: Secure Password Tracking for Android

Security'14

原文链接
作者单位：杜克大学

Abstract

本文提出的SpanDex，实现了一个Android DVM的扩展集，可以完整、准确、快速地处理Android程序中的隐式信息流，保证应用程序不泄露用户的密码。作者通过符号执行中的方法，量化隐式信息流揭露出的关于secret的信息。为了不影响性能，SpanDex将不受信任的代码运行在一个数据流敏感的沙箱里，以限制程序可以对敏感数据执行的操作。作者在SpanDex上运行了50个应用，其中42个没有出现异常，并且发现攻击者恢复出密码平均需要80次尝试，而在没有使用Spandex的情况下，只需要一次尝试。

Background

• 污点跟踪（Taint Tracking）
  monitor为每个存储对象维护一个标签（label），并在执行过程中动态更新对象的标签，以表明哪些系统状态中有秘密信息。
• 显式信息流
  秘密信息直接从一个操作的原操作数传递到目的操作数，如x = s。

• 隐式信息流
  秘密信息通过程序的控制流传递，如if s ！= 0 then x = a中，除了从a到x的信息流，还有一条从s到x的隐式信息流。

  污点跟踪要考虑的问题：完整性（Soundness）【no false negative】，准确性（Precision）【no overtainting，false positive】和效率（Efficiency）

  现有工作

• 静态分析与secrecy-aware type system和程序员定义的declassifier相结合，这种方式sound，precise，efficient，但是需要在程序中添加secrecy annotation和declassifier。

• 在较高层次的操作上传播污点，这种方式sound，efficient，但是操作参数的粒度与带标签粒度的不匹配会导致imprecision，并且也同样需要declassifier来提高准确度。
• 对于if s != 0 then x := a else y := b done，s是含有秘密信息的变量，then和done之间的操作叫做enclosed region，受影响的对象集叫做enclosed set。对了保证完整性，monitor要把s的tag传递给集合中的所有对象。但是这样会造成overtainting。
  DTA++和Flowcheck都关注了这个问题，DTA++在只有控制流完全揭露秘密信息的情况下，才把tag传递给集合中的对象，但有两个方面的问题：一是在处理password这类信息时，虽然没有完全揭露，但部分信息被揭露也是有问题的；二是DTA++依赖离线符号执行，采用一些有代表性的输入来选择那些分支应该传递tag，这种方式会有代码覆盖不足的问题，不大可能阻止恶意程序。
  Flowcheck准确的量化了控制流揭示的秘密信息的数量，但是对性能有很大影响，并且通常需要程序员的帮助来计算enclosed set，以此来量化enclosed region的channel capacity。

Android-app Study

为了证明传统处理隐式信息流的方法会带来overtainting，作者在TaintDroid和TaintDroid的修改版（TaintDroid++）这两个执行环境上运行4个应用程序。TaintDroid只做显式信息流跟踪，而TaintDroid++支持隐式信息流跟踪。在输入password后，检查tainted output。

SpanDex

• 信任和攻击模型
  
  • SpanDex是在Dalvik虚拟机接口之下实现的，因此虚拟机提供的保护提供了SpanDex的信任模型基础。SpanDex无法对使用第三方native code的应用进行密码保护
    
    • 被taint的对象在应用执行native code前要被清理
    • 进程调用第三方native code后，就不被允许接收密码数据（SpanDex依赖内核维护进程调用native code的信息）
    • 应用不能把tainted数据写到永久存储去，或者通过IPC发送给其他应用
  • SpanDex关注密码数据在应用内的流向
    
    • 用户将密码和对应的域打标签
  • 确保密码数据只跟域内的服务器共享，但是在数据离开设备后，不提供任何保证。例如SpanDex无法阻止攻击者将用户的facebook密码作为一条消息发送给攻击者控制的Facebook账户
  • 攻击模型
    
    • 攻击者知道用户的用户名，并且假定用户的密码是一个很大的list中的一个，攻击的目标就是使用应用中获得的信息，从密码list中找到用户的密码。一旦攻击者计算出一个用户名可能的密码集，找出真正密码的方法就是在线查询。

设计原则

1. 对于显式控制流和隐式控制流分开处理。
   触发显式控制流的操作将相对数量较大的信息量传递给几个对象，而隐式信息流会将相对较少的信息量传递给对象数目很多的enclosed set。
   SpanDex用传统的污点跟踪方式处理显式流。而在遇到带有污点的条件分支时，并不是把污点传播到enclosed set中的对象，而是计算到目前为止控制流已经揭露的信息量（上界）。若认为此信息量安全，则忽略污点在enclosed region中的传播。
   SpanDex会记录下从变量的当前状态到初始秘密信息的操作序列，在遇到带污点的条件分支时，利用这个序列解CSP（Constraint Satisfaction Problem）问题，更新上界。
2. 如果常见的程序功能使解CSP问题开销过大，则强迫程序使用可信的实现。
   一些密码学或编码操作会有大量的bit-wise或array-indexing操作与条件分支交织在一起，使得解CSP问题需要很大的工作量。
   SpanDex对可信库中的代码只进行显式信息流跟踪，并对于用户自己实现的密码学操作，在加密tainted数据时，强迫使用可信密码库。
3. 使用秘密信息的数据类型特性来设置release policy。
   对于password来说，只要保证控制流揭示出的每个字符的可能范围不小于可见字符集合，就可以release。

具体实现

SpanDex把每个秘密信息可能的取值范围叫做p-set（possibility set）。为了缩小p-set的范围，需要知道从原始秘密信息到一个tainted条件分支过程的数据流。op-dag就反映了这种依赖关系。
SpanDex的label是一个纸箱op-dag中节点的指针。
op-dag的root节点包含原始秘密信息，p-set和domain（表明秘密信息可以发往哪个domain）。
op-dag的普通节点node记录操作，操作数等信息。

Evaluation

密码保护

50个应用（8个不能在SpanDex上正确运行），选取一个长度为35的密码。下图是运行完42个应用程序后对密码中每个字符得到的p-set的大小分布情况

可以看到'A','a','0'的p-set大小不会小于26和10，而'*','-','.','_'对于75%的应用都有较大的p-set。

为了模拟实际攻击，作者选取了uniqpass-v11中的131M的密码表，计算其中某一个密码p在某一程序中暴露出的p-set。假设攻击者已知p的长度，和每个字符的情况（也就是每个字符是否是大写字母，小写字母，数字，特殊字符）。也就是说p可以由一个正规表达式表示，那么就可以计算match set和match count。match set的大小表明在攻击者无法缩小p-set的情况下，是不大可能猜到密码的。

但实际情况中密码的使用服从zipf分布，也就是说match set中的密码是用户密码的概率不同。
几个密码库的密码符合zipf分布，并且参数s的值分别是0.246，0.695，0.23和0.7878。
作者使用这些值，对math set中的密码进行建模，并计算出了尝试次数的CDF。

性能开销