不要说话
0%

发表于 更新于 分类于

最近准备学习一下调试技术，为以后的逆向分析打下基础，主要关注是Linux平台下的软件调试。现在列举一些调试相关的书籍，一边看书，一边实践。

  1. 软件调试的艺术（The Art of Debugging with GDB,DDD, and Eclipse）, 2009.11
  2. 软件调试实战 （The Developers Guide to Debugging）, 2010.2
  3. Debug It! Find, Repair, and Prevent Bugs in Your Code , 2011.6
  4. 格蠹汇编 —— 软件调试案例集锦

发表于 更新于 分类于

最长回文子串是字符串处理中最经典的问题之一，其解决方法有多种，效率也不一样。下面分别介绍几种解决方法。

0x01. 动态规划

时间复杂度：o(n^2), 空间复杂度：o(n^2).
动态规划方程：

1
2
3
4
5
dp[i][j] 表示子串s[i…j]是否是回文
初始化：
   dp[i][i] = true (0 <= i <= n-1);
   dp[i][i-1] = true (1 <= i <= n-1); 其余的初始化为false
dp[i][j] = (s[i] == s[j] && dp[i+1][j-1] == true)

0x02. Manecher算法

时间复杂度：o(n), 空间复杂度：o(n).
该算法首先对字符串进行预处理，在字符串的每个字符前后都加入一个特殊符号，比如字符串 abcb 处理成#a#b#c#b#。为了避免处理越界，在字符串首尾加上不同的两个特殊字符（C类型的字符串后面有’\0’，不用加），最后预处理的字符串为^#a#b#c#b#。
就以上面的字符串为例，经过预处理后，变成s= “^#a#b#c#b#”;
设数组p[i]的值为以字符s[i]为中心的最长回文子串向两边扩展的长度（包括s[i]）,以上述字符串为例：

1
2
3
s:  ^ # a # b # c # b #
p:    1 2 1 2 1 4 1 2 1

仔细观察可以发现，p[i]-1 正好是原字符串中回文串的总长度。
p[]数组的求法：
设id是当前求得的最长回文子串中心的位置，mx是当前最长回文子串的右边界（回文子串不包括该右边界），即mx = id + p[id]。设i是id右边的位置，则关于id对称的点j = id-(i-id)= 2*id-i。

  1. 当 mx > i 时：
    如果 mx-i > p[j], 则以s[j]为中心的回文子串包含在以s[id]为中心的回文子串中。由于i和j对称，那么以s[i]为中心的回文子串必然包含在以s[id]为中心的回文子串中。所以至少 p[i]>=p[j]，后面的在继续匹配。
    如果 mx-i <= p[j], 则以s[j]为中心的回文子串不完全包含于以s[id]为中心的回文子串中。但由于对称性，以s[i]为中心的回文串，其向右至少会扩展到mx的位置，即p[i]至少等于 mx-i,至于后面的部分是否对称，只好一一匹配。
  2. 当 mx <= i 时：
    无法对p[i]做更多的假设，只能p[i] = 1, 然后再去匹配。
    上述过程的C语言实现如下： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //输入预处理的字符串s
    int p[MAXN], mx = 0, id = 0;
    memset(p, 0, sizeof(p));
    for (i = 1; s[i] != '\0'; i++) {
        p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
        while (s[i + p[i]] == s[i - p[i]]) p[i]++;
        if (i + p[i] > mx) {
            mx = i + p[i];
            id = i;
        }
    }
    //找出p[i]中最大的

0x03. 后缀数组（后缀树）

待续。。。

发表于 更新于 分类于

搜索算法是最基础的算法，比较实用。枚举搜索是最简单的搜索算法，适用于问题规模比较小的情景。下面用一道题熟悉一下，搜索24点。

题目来源：http://hihocoder.com/contest/hiho98/problem/1

C实现的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<stdio.h>
#include<string.h>

int  used[4], nowNumber[4], number[4];

// ^'表示反减,'|'表示反除，
char ops[3], opType[6] = {'+','-','*','/','^','|'};

float operate(char op, float a, float b){
	float t;
	switch(op){
        case '+' : t = a+b; break;
    	case '-' : t = a-b; break;
    	case '*' : t = a*b; break;
    	case '/' : {
    		if(b<0 || b>0)
    		    t = a/b;
    		break;
    	}
    	case '^' : t = b-a; break;
    	case '|' :{
    		if(a<0 || a>0)
    		   t = b/a;
    		break;
    	}
	}
	return t;
}

//计算类型一表达式：((a@b)@c)@d
float calcType1(){
	int i;
	float tmp;
	tmp = nowNumber[0];
	for(i=0; i<3; ++i){
    	tmp = operate(ops[i], tmp, nowNumber[i+1]);
	}
	return tmp;
}

//计算类型二表达式：(a@b)@(c@d)
float calcType2(){
    float t,m,n;
    m = operate(ops[0], nowNumber[0], nowNumber[1]);
    n = operate(ops[2], nowNumber[2], nowNumber[3]);
    t = operate(ops[1], m, n);
	return t;
}

int makeOperation(int depth){
	int i;
	if(depth >= 3){
		//计算类型一
		if(calcType1()>=24 && calcType1()<=24)
			return 1;
		//计算类型二
		if(calcType2()>=24 && calcType2()<=24)
			return 1;
        return 0;
	}

	for(i=0; i<6; ++i){
		ops[depth] = opType[i];
		if(makeOperation(depth+1))
			return 1;
	}

	return 0;
}

int makeNumber(int depth){
    int i;
    if(depth >= 4)
    	return makeOperation(0);

    for(i=0; i<4; ++i){
    	if(used[i] == 0){
           nowNumber[ depth ] = number[i];

           used[i] = 1;
           if(makeNumber(depth+1)){
           	    return 1;
           }
           used[i] = 0;
    	}
    }
    return 0;
}

int main(){
	int i,t;

	while(scanf("%d", &t) != EOF){
       for(i=0; i<t; ++i){
          scanf("%d %d %d %d", &number[0], &number[1], &number[2], &number[3]);
          memset(used, 0, sizeof(used));
          if(makeNumber(0) == 1)
          	printf("Yes\n");
          else
          	printf("No\n");
       }
	}
	return 0;
}

发表于 更新于 分类于

字典树用于单词统计，查询，非常有用。现在就Trie树给出C语言实现。

题目来源：http://hihocoder.com/problemset/problem/1014

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <malloc.h>

#define MAXN  26

struct Trie{
	int count;   //单词计数
	int flag;    // 1表示是单词，0表示不是单词
	struct Trie *next[MAXN];
};

struct Trie *rt;

//初始化Trie树
void trie_init(){
	int i;
	rt = (struct Trie*)malloc(sizeof(struct Trie));

	rt->count = 0;
	rt->flag = 0;
	for(i=0; i<MAXN; ++i)
		rt->next[i] = NULL;
}

//插入单词
void trie_insert(char *s){
	int i;
	struct Trie *tmp = rt;

	for(s; *s!='\0'; ++s){
		if(tmp->next[*s -'a'] == NULL){
             struct Trie *cur = (struct Trie*)malloc(sizeof(struct Trie));
             cur->count = 0;
             cur->flag = 0;
             for(i=0; i<MAXN; ++i)
		         cur->next[i] = NULL;
		     tmp->next[*s -'a'] = cur;
		}
		tmp->count++;
		tmp = tmp->next[*s -'a'];
	}
	tmp->flag = 1;
	tmp->count++;
}

//查询给定字符串前缀的单词数目
int trie_search(char *s){

	struct Trie *tmp = rt;
	for(s; *s!='\0'; ++s){
		if(tmp->next[*s -'a'] == NULL)
			return 0;
	    tmp = tmp->next[*s -'a'];
	}
	return tmp->count;
}

//删除整个Trie树
void trie_del(struct Trie *root){
    int i;
    for(i=0; i<MAXN; ++i){
       if(root->next[i] != NULL)
       	trie_del(root->next[i]);
    }
    free(root);
}

int main(){
  	int i, n, m;
	  char ch[15];

    FILE *fin;
    fin = fopen("input.txt", "r");

 while(fscanf(fin, "%d", &n) != EOF){
       trie_init();
       for(i=0; i<n; ++i){
       	   fscanf(fin, "%s", ch);   	  
       	   trie_insert(ch);
       }
       fscanf(fin, "%d", &m);
       for(i=0; i<m; ++i){
		   fscanf(fin, "%s", ch);
       	   printf("%d\n", trie_search(ch));
       }
       trie_del(rt);
	 }  

	return 0;
}

发表于 更新于 分类于

最近花了一点时间看完《正则表达式必知必会》，记录下学习的知识点。正则表达式主要是用于处理文本，用于搜索和替换。

0x01. 匹配单个字符

（1） 匹配纯文本

1
2
3
4
#文本
Hello, my name is Ben. Please visit my website at http://www.forta.com
#正则表达式
Ben

（2）匹配任意字符 ( 使用元字符. )
（3）匹配特殊字符 (使用转义字符\ 转义元字符)

0x02. 匹配一组字符

（1）匹配多个字符中的某一个 ( 使用元字符[和]，如[ns])
（2）利用字符集合区间 (使用元字符- ，如：[A-Za-z0-9] )
（3）取非匹配 ( 使用元字符^，如：[^0-9])

0x03. 使用元字符

(1) 对特殊字符进行转义 (使用转义字符)
(2) 匹配空白字符

1
2
3
4
5
6
7
8
| 元字符    |    说明    |
| -------  | :-------: |
| [\b]     | 回退（并删除）一个字符（Backspace键）|
| \f       | 换页符|
| \n       | 换行符|
| \r       | 回车符|
| \t       | 制表符（Tab键）|
| \v       | 垂直制表符|

(3) 匹配特定的字符类别
1）匹配数字（与非数字）

1
2
\d    匹配任何一个数字字符（等价于[0-9]）
\D   匹配任何一个非数字字符（等价于[^0-9]）

2）匹配字母和数字（与非字母和数字）

1
2
\w    匹配任何一个字母数字字符（大小写均可）或下划线（等价于[a-zA-Z0-9_]）
\W   匹配任何一个非字母数字或下划线字符（等价于[^a-zA-Z0-9_]）

3）匹配空白字符（与非空白字符）

1
2
\s    匹配任何一个空白字符（等价于[\f\n\r\t\v]）
\S    匹配任何一个非空白字符（等价于[^\f\n\r\t\v]）

(4) 使用POSIX字符类
POSIX字符类是许多（但不是所有）正则表达式实现都支持的一种简写形式。

0x04. 重复匹配

  1. 有多个匹配
    1) 匹配一个或多个字符（使用元字符 +）
    2）匹配零个或多个字符（使用元字符 *）
    3）匹配零个或一个字符（使用元字符 ?）
  2. 匹配的重复次数
    1) 为重复匹配次数设定一个精确的值（如：{3}）
    2) 为重复匹配次数设定一个区间（如：{3-9}）
    3) 匹配“至少重复多少次”（如：{3, }）
  3. 防止过度匹配
    在进行模式匹配的时候会出现一种过度匹配的现象：在文本中匹配 <[Bb]>.*</[Bb]>时，会匹配第一个或到最后一个或之间的所有字符。原因：*和+都是所谓的“贪婪型”元字符，它们在进行匹配时的 行为模式是多多益善而不是适可而止。

解决的方法：使用元字符的”懒惰型”版本，即在元字符后面加一个?后缀。

1
2
3
4
贪婪型元字符         懒惰型元字符
    *                  *?
    +                  +?
  {n, }            (n, )?

0x05. 位置匹配

(1) 单词边界 （使用元字符 \b表示，如：\bcat\b）

1
2
3
4
5
6
#文本
The caption wore his cap and cape proudly as he sat listening to the recap of how his crew saved the men from a capsized vessel.
#正则表达式          匹配结果
 \bcap\b           cap
 \bcap             captain cap cape capsized  
 cap\b             cap recap

(2) 字符串边界（使用元字符^和$分别表示字符串的首和尾）

1
2
3
4
5
6
7
#文本
<?xml version="1.0" encoding="UTF-8" ?>
<wsdl:definitions targerNamespace="http://tips.cf"
xmlns:impl="http://tips/cf" xmlns:intf="http://tips.cf"
xmlns:apachesoap="http://xml.apache.org/xml.soap"
#正则表达式
^\s*<\?xml.*\?>     匹配第一行

0x06. 使用子表达式

(1) 子表达式 (使用元字符(和)包含表达式)
(2) 子表达式的嵌套

0x07. 回溯引用：前后一致匹配

(1) 回溯引用匹配

1
2
3
#正则表达式
[ ]+(\w+)[ ]+\1
<[hH](1-6)>.*?</[hH]\1>    #.*?表示懒惰型.*匹配

(2) 回溯引用在替换操作中的应用

1
2
3
4
#正则表达式                            
(\w+[\w\.]*@[\w\.]+\.\w+)       
#替换
<A HREF="mailto:$1">$1</A>

0x08. 前后查找

(1) 向前查找（以 ?= 开头的子表达式）

1
2
3
4
5
6
#文本
http://www.forta.com/
https://mail/forta.com/
ftp://ftp.forta.com/
#正则表达式        结果
.*(?=:)        http https ftp   #?=表示：只要找到：就行了，不要把它包括在最终的匹配结果里。

(2) 向后查找（以 ?<= 开头的子表达式）

1
2
3
4
5
6
7
8
#文本
ABC01:  $23.45
HGG42:  $5.31
CFMX1:  $899.00
XTC99:  $69.96
Total items found: 4
# 正则表达式         结果
(?<=\$)[0-9.]+     23.45  5.31 899.00 69.96

(3) 对前后查找取非
负向前查找将向前查找不与给定模式匹配的文本，负向后查找将向后查找不与给定模式匹配的文本。

1
2
3
4
5
6
7
8
9
10
11
12
操作符          说明
(?=)          正向前查找
(?!)          负向前查找
(?<=)         正向后查找
(?<!)         负向后查找    
#文本
I paid $30 for 100 apples, 50 oranges, and 60 pears.
I saved $5 on this order.

#正则表达式                   
(?<=\$)\d+          #向后查找价格
\b(?<!\$)\d+\b      #只查找数量

0x09. 嵌入条件

正则表达式里的条件要用?定义。
?匹配前一个字符或表达式，如果它存在的话。
?=和?<=匹配前面或后面的文本，如果它存在的话。
嵌入条件语法也使用了?，嵌入条件的两种情况：1) 根据一个回溯引用来进行条件处理；2）根据一个前后查找来进行条件处理。
（1）回溯引用条件
定义这种条件的语法是：(?(backreference)true-regex|false-regex) ；也可以只用前面的true-regex;

1
2
3
4
5
6
7
8
9
10
11
12
#文本
123-456-7890
(123)456-7890
(123)-456-7890
(123-456-7890
1234567890
123 456 7890
#正则表达式    匹配美式电话号码
(\()?\d{3}(?(1)\)|-)\d{3}-\d{4})   
#结果
123-456-7890
(123)456-7890

（2）前后查找条件
定义这种条件的语法类似上面，只需把回溯引用替换为一个完整的前后查找表达式就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
#文本  美国的邮政编码两种格式：12345形式的ZIP格式;12345-6789形式的ZIP+4格式
11111
22222
33333
44444-
55555-5555
#正则表达式
\d{5}(?(?=-)-\d{4})    #匹配美式邮编
#结果
11111
22222
33333
55555-5555

发表于 更新于 分类于

最近在学习Android SO库逆向方面的知识，以2016腾讯游戏安全竞赛第一轮Android题练手，参考了一些资料，其中也有些不足的地方，希望未来好好学习逆向方面的知识。

0x01.　分析思路

本题用JEB看了一下，对于输入的Name和Code进行验证，主要的验证逻辑在SO库中。因此直接逆向SO库，找到导出的函数NativeCheckRegister(String name, String code)。

0x02.　SO库逆向

根据对SO中NativeCheckRegister函数的分析，该函数对Name字符串处理了2次，产生长度为20的字符数组；对Code字符串处理了1次，也产生长度为20的字符数组；做好对这两个数组进行比较。

  1. 对Name字符串的第一次处理
    函数刚开始就检查输入字符串Name的长度，是否在6和20之间；然后对Name字符串进行第一次处理，得到长为20的字符串。处理过程：每次会从Name字符串取一个字节，操作公式为：字节×(0x1339e7e+循环次数)×Name长度+上一次得到的4字节高3字节（第一次为0），然后将得到的4字节的低字节存入新数组。循环次数为0x10次，多出来的4个长度为维护得到的4字节数的高3字节以及一个0。

  2. 对Code字符串的处理
    在对Code字符串进行处理时用了2个子例程，分别是sub_146c和sub_1498。sub_1498是对注册码进行一些操作，得到一个数组；之后对数组长度进行判断，是否为0x14(即20)，等于0x20则进行后面的处理；反之直接结束。

sub_1498子例程处理过程：
该子例程传入的参数是 Code字符串首地址(R1) 和 **栈上新数组首地址(R0)*；
执行流程: 先通过查表操作判断Code字符串是否满足约束条件（Code字节对应的表值不能超过0x3F），如果不满足，则进行截断。因此查询的表需要dump下来，后面的字符串也要用到这个表。然后对满足约束条件的字符串进行处理。将字符串以4字节为单位，进行处理生成新的3字节字符存入栈上新数组；不足4字节的，分别进行一下处理：剩下1字节，直接退出；剩下2字节，经过操作生成1字节退出；剩下3字节，经过操作生成2字节退出；根据前面的数组长度要求为0x14,可以推断出注册码长度必须为27位：20/3=6…2 , 64+3 = 27 。
将字符串以4字节为单位操作的步骤：
1）通过查表，将第1个字节对应的表值逻辑左移2位，与第2个字节对应的表值逻辑右移4位进行或运算，产生第1个新字节；
2）通过查表，将第2个字节对应的表值逻辑左移4位，与第3个字节对应的表值逻辑右移2位进行或运算，产生第2个新字节；
3）通过查表，将第3个字节对应的表值逻辑左移6位，与第4个字节对应的表值进行或运算，产生第3个新字节；

  1. 对Name字符串的第二次处理
    将20位的Name字符串数组，每个元素除以0xA,然后重新保存。

  2. 比较
    将Name进行2次操作生成的长度20的数组，与注册码进行了1次操作生成的长度20的数组进行5次比较；
    根据5次比较，设Name每4字节对应一个变量，那么就有5个已知的变量a1(对应数组0x00)、a2(0x04)、a3(0x08)、a4(0x0c)、a5(0x10);设注册码的20位数组每4个字节对应一个未知变量，那么就有5个未知变量x1(0x00)、x2(0x04)、x3(0x08)、x4(0x0c)、x5(0x10);根据比较列出方程：

    1
    2
    3
    4
    5
    1) a1 + x5 = x3
    2) a2 + x5 + a1 = x5 * 2
    3) x4 + a3 = x1
    4) a4 + x4 + a3 = x4 * 2
    5) x2 + a5  = a3 * 3

发表于 更新于 分类于

最近在学习Android逆向相关的知识，了解APK的保护方法对逆向有很大的帮助。

0x01.　Dex完整性校验

classes.dex 在 Android 系统上基本负责完成所有的逻辑业务，因此很多针对 Android 应用程序的篡改都是针对 classes.dex 文件的。在 APK 的自我保护上，也可以考虑对 classes.dex文件进行完整性校验，简单的可以通过 CRC 校验完成， 也可以检查 Hash 值。由于只是检查classes.dex，所以可以将 CRC 值存储在 string 资源文件中，当然也可以放在自己的服务器上，通过运行时从服务器获取校验值。基本步骤如下：

  • 首先在代码中完成校验值比对的逻辑，此部分代码后续不能再改变，否则 CRC 值会发生变化；
  • 从生成的 APK文 件中提取出 classes.dex 文件，计算其 CRC 值，其他 hash 值类似；
  • 将计算出的值放入 strings.xml 文件中。

0x02.　APK完整性校验

虽然 Android 程序的主要逻辑通过 classes.dex 文件执行，但是其他文件也会影响到整个程序的逻辑走向，以上述 Dex 文件校验为例，如果程序依赖 strings.xml 文件中的某些值，则修改这些值就会影响程序的运行，所以进一步可以整个 APK 文件进行完整性校验。 但是如果对整个 APK 文件进行完整性校验，由于在开发 Android 应用程序时，无法知道完整 APK 文件的 Hash 值，所以这个 Hash 值的存储无法像 Dex 完整性校验那样放在 strings.xml 文件中，所以可以考虑将值放在服务器端。

0x03.　模拟器检测

一般在分析 APK 的过程中会借助于 Android 模拟器，比如分析网络行为，动态调试等。因此从 APK 自我保护的角度出发，可以增加对 APK 当前运行环境的检测，判断是否运行在模拟器中，如果运行在模拟器中可以选择退出整个应用程序的执行或者跳到其他分支。模拟器检测的手段有很多，下面逐一分析。

  1. 属性检测
    Android 属性系统类似于 Windows 的注册表机制， 所有的进程可以共享系统设置值 一些属性值在 Android 模拟器和真机上是不同的，根据这些属性值在真实机器和模拟器上的差别可以比较容易的。
  2. 虚拟机文件检测
    相对于真实设备，Android模拟器中存在一些特殊的文件或目录，如/system/bin/qemu-props,该可执行文件可以用来在模拟器中设置系统属性。 另外还有/system/lib/libc_malloc_debug_qemu.so 文件以及/sys/qemu_trace 目录。我们可以通过检测这些特殊文件或者目录是否存在来判断 Android 应用程序是否运行在模拟器中。

0x04.　调试器检测

在对 APK 逆向分析时，往往会采取动态调试技术，可以使用 netbeans+apktool 对反汇编生成的 smali 代码进行动态调试。为了防止 APK 被动态调试，可以检测是否有调试器连接。Android 系统在 android.os.Debug 类中提供了 isDebuggerConnected()方法，用于检测是否有调试器连接。可以在 Application 类中调用 isDebuggerConnected()方法，判断是否有调试器连接，如果有，直接退出程序。
除了 isDebuggerConnected 方法，还可以通过在 AndroidManifest 文件的 application 节点中加入 android:debuggable=”false”使得程序不可被调试，这样如果希望调试代码，则需要修改该值为 true，因此可以在代码中检查这个属性的值，判断程序是否被修改过，

发表于 更新于 分类于

Kali Linux 安装后的配置，首先更换Kali Linux国内的软件源。

0x01.　Kali Linux更换源

中科大kali源

1
2
3
deb http://mirrors.ustc.edu.cn/kali sana main non-free contrib
deb http://mirrors.ustc.edu.cn/kali-security/ sana/updates main contrib non-free
deb-src http://mirrors.ustc.edu.cn/kali-security/ sana/updates main contrib non-free

阿里云kali源

1
2
3
deb http://mirrors.aliyun.com/kali sana main non-free contrib
deb http://mirrors.aliyun.com/kali-security/ sana/updates main contrib non-free
deb-src http://mirrors.aliyun.com/kali-security/ sana/updates main contrib non-free

对软件进行一次整体更新：

1
2
3
$ apt-get update & apt-get upgrade
$ apt-get dist-upgrade
$ apt-get clean

0x02.　Kali Linux安装中文输入法（以下任选）

拼音五笔

1
$ apt-get install fcitx-table-wbpy ttf-wqy-microhei ttf-wqy-zenhei

经典的ibus

1
$ apt-get install ibus ibus-pinyin

fcitx拼音

1
$ apt-get install fcitx fcitx-googlepinyin

如果安装出现问题，可能是因为没有软件源，依赖问题。解决方法：

1
2
$ aptitude update
$ aptitude install ibus ibus-pinyin