Programming

比较两个文件的相同

恐怕地球人都知道比较两个文件的不同得用diff(1),现在有个问题是:如何找出两个文件的相同之处?

经过简单查找,我发现可以用comm(1)。可是看了一下它的man我们就发现,不妥,它没diff(1)那么简单。首先它的选项有些特别;其次,很重要的是,它要求文件必须是排好序的!这时候恐怕我们就得想,哎,又得用bash脚本了。不行,那不符合hack精神,我就不信在一行里整不出它来!于是下面的一行就出来乐:

% comm -1 -2 <(cat 1.txt | sort) <(cat 2.txt |sort)

或者更干脆:

% comm -1 -2 <(sort 1.txt) <(sort 2.txt)

zsh和bash都可以用的。可见,shell语法是够博大精深的……

课后作业:不看源代码,猜猜上面的技巧大体上是怎么实现的?(想知道“答案”的拖住最后一行。;-)

提示:把comm换成diff看看,是不是用的/proc/self?

跨行搜索脚本:mgrep

写了做跨行搜索的脚本,用Perl。我知道也可以在bash里用sed,但我认为用那的话灵活性就不如用Perl了,因为我还要给它扩展各种我需要的功能。

闲话少说,上代码!

[perl]

!/usr/bin/perl -w

From: http://www.kclug.org/pipermail/kclug/2005-June/028106.html

Hacked by WANG Cong.

Copyright (C) 2008, WANG Cong

Usage

mgrep.pl -s -e [—nonum]

use strict;
use warnings;
use Getopt::Long;

my($start, $end, $file);
my $num = 1;

my $allow_nest = 0;

my $allow_recursion = 0;
my $allow_binary = 0;

GetOptions(
“start=s” => $start,
“end=s” => $end,
“nonum” => sub { $num = 0; },
“recursion” => sub { $allow_recursion = 1 },
“binary” => sub { $allow_binary = 1 }

“nest” => sub { $allow_nest = 1; }

);

$file = shift;

die “$start and $end options are both required. And so is the file name.”
unless ($start && $end && $file);

my $start_reg = eval {qr/$start/};
die “The start pattern is not correct!” if $@;
my $end_reg = eval {qr/$end/};
die “The end pattern is not correct!” if $@;

## sub

sub mgrep_file
{
my @matches;

#my @nest_stack;
my $matching; #boolean
my $added = 0; #boolean
my $linecount = 0;
my $file = shift;

open( IN, $file ) or return undef;

while( my $line = readline *IN)
{
$linecount++;
if( $line =~ /($start_reg.*)/ )
{
    $matching = 1;
    if(!$added){
    push @matches, "==", $file, "==n";
    $added = 1;
    }
    if ($num) {
    push( @matches, $linecount . ": " . $1 . "n" );
    }else{
    push( @matches, $1 . "n" );
    }

    if( $1 =~ /$end_reg/){ $matching = 0; }
    next;
}

if( $matching )
{
    if( $line =~ /(.*$end_reg)/ )
    {
    if ($num){
        push( @matches, $linecount . ": " . $1 . "n" );
    }else{
        push( @matches, $1 . "n" );
    }
    $matching = 0;
    }
    else
    {
    if ($num){
        push( @matches, $linecount . ": " . $line );
    }else{
        push( @matches, $line);
    }
    }
}
}
close IN;
return @matches;

}

sub mgrep_dir
{
my $dir = shift;
my @file_list;
my @match_list = ();
my $ret;
my @lret;

opendir(IN_DIR, $dir) || return undef;
@file_list = grep { $_ ne '.' and $_ ne '..' } readdir IN_DIR;

if (@file_list){
for my $one (@file_list) {
    my $fname = "$dir/$one";
    if (-f $fname){
    next if(!-T $fname &amp;&amp; !$allow_binary);
    $ret = mgrep_file($fname);
    next unless @$ret;
    push @match_list, @$ret;
    }
    if ($allow_recursion &amp;&amp; -d $fname){
    @lret = mgrep_dir($fname);
    next unless @lret;
    push @match_list, @lret;
    }
}
}

closedir IN_DIR;
return @match_list;

}

##### main

while ($file)
{
my $ret;
my @list;

if (-f $file){
next if(!-T $file &amp;&amp; !$allow_binary);
$ret = mgrep_file($file);
print @$ret;
}
elsif (-d $file){
@list = mgrep_dir($file);
print @list;
}else{
die "$file is not existed!";
}

$file = shift;

}

[/perl]

Python和Perl都没消除自指?

[perl]

!/usr/bin/perl

use strict;
use warnings;

my @foo = qw(foo1 foo2);
my @bar = qw(bar1 bar2);

push @foo, @bar;
push @bar, @foo;

print @{$foo[2][2][2][2][2][2][2][2][2][2]}, “n”

please add more if you want

[/perl]

[python]

!/usr/bin/env python

foo = [‘foo1’, ‘foo2’]
bar = [‘bar1’, ‘bar2’]

foo.append(bar)
bar.append(foo)

print foo[2][2][2][2][2][2][2]

please add more if you want

[/python]

C语言显然不会出现这种情况,因为要用指针的话这两种指针显然不是一个层次上的,必须通过强制转化。而Python和Perl之所以都会出现这种情况是因为他们的的list都太NB了,啥都能放,包括它本身!!

或者是我最近看《集异璧》看多了??

发布Qbak项目

Qbak 是 “Quick Backup” 的缩写。Qbak 是 Linux 上使用的备份工具,目前只有 命令行界面。但我会考虑以后为它加入图形界面。

Qbak 的使用和配置非常简单,它读取~/.qbakrc作为配置文件,并把里面指定的目录作为“输出目录”,即存放备份文件归档的目录。建议设置为”~/.qbak”。 关于配置项请看源代码中的示例配置文件。

Qbak 使用了一种半“堆栈式”的管理方式,即通过push和pull来加入和导出备份文件。Qbak 的接口有点像git,通过其子命令来完成各种功能。想了解更多请去项目主页

现在 Qbak 还不成熟,有一些小bug,还有许多待完善的地方。Qbak 是用bash脚本写成的,欢迎有兴趣的同学加入!!

下载地址:
http://wangcong.org/projects/qbak-0.1.tar.gz

Qbak 项目主页:
http://wangcong.org/projects/qbak.html

assembler的一个hack

如果编译一个relocatable目标文件,你通过反汇编不难发现所有的call指令竟然都是同一个机器码!即:e8 fc ff ff ff。

我们知道,不同的函数有不同的入口,可这里怎么都会用这么一个奇怪的地址呢?

翻一下Intel指令手册,我们很容易就能在3-104 Vol. 2A中找到call指令的各种编码方式。根据这里的opcode为e8我们不难确定这个call是用的下面这种方式:

E8 cd CALL rel32

这就告诉我们,opcode后面其实是一个32位相当的相对地址。如果你肯在往后翻几页的话,就会发现这种方式的执行过程,如下:

tempEIP ←EIP +DEST; ( DEST is rel32 )
IF tempEIP is not within code segment limit THEN #GP(0); FI;
IF stack not large enough for a 4-byte return address
THEN #SS(0); FI;
Push(EIP);
EIP ←tempEIP;

也就是说会用当前的EIP加上那个相对地址作为最终的call转移地址。别慌,还没完,我们继续。

我们知道,relocatable目标文件的符号地址都是不能使用的,因为还没经过linker转化。linker转化后的地址才是最终的地址,也就是说从上面那个地址到最后的地址还有一段过程,由ld来完成。

我们知道,这里正确的地址应该是该符号实际的地址与这个call地址之间的偏移。而这等于这个函数的实际入口与.text section之间的偏移减去这个符号相对.text的偏移!后者由ELF格式直接给出,而前者也很容易计算。

到这里你会发现,不对,我们那个fc ff ff ff还没用上!是,因为我们前面忽视了很重要的一点,EIP是指向下一条指令的而不是当前这条的地址!也就是说,我们前面的结果需要修正!具体说是需要修正一个 -0x4。再看一下fc ff ff ff,不正是-4么?!(x86是little endian!)对,正是这个由assembler故意安排的-4修正了我们call指令!

当然了,如果符号不是一个函数地址,而是一个全局变量的地址,这就不需要修正,相应的relocatable文件里就是0。

不得不说这是一个很聪明的hack!

还有,如果你看最后executable文件,你可能又困惑了,call后面的修正似乎和上面不一样。举个例子:

80483ba:       e8 18 00 00 00          call   80483d7 <foo>

0x80483ba+0x18明显不是0x80483d7。嘿嘿,这里就不一样了,因为这里需要修正的是-0x5。差的那个会是啥呢?猜猜吧?(用鼠标拖住最后一行看答案。;-)

就是那个e8啊!

又hack了一个shell脚本

正如董溥同学给我留的言,coolcode插件不支持C语言,这是事实。而且用coolcode插件往wordpress里贴代码也是不很爽~!

于是乎,我就hack了一个脚本,调用vim来生成html,然后往博客里贴时复制里面的html代码就是了。恩,我知道emacs有个htmlize插件,可惜它生成的html是CSS的,貌似wordpress不支持直接贴那玩意(未经验证)。我用它更新了一下前面一篇文章中的代码,效果还不错,代码如下:

#!/bin/bash #Copyright(C) 2008, WANG Cong #GPLv3 applies. if (($# != 1)) ; then

        echo "Bad usage!"

        exit 1

fi if [ ! -f $1 ] ; then

        echo "$1: No such file!"

        exit 2

fi

vim -n -c :so $VIMRUNTIME/syntax/2html.vim -c ":w $1.html" 

        -c ":qa" $1  > /dev/null 2> /dev/null

exit 0

一个实用的shell脚本

刚写的一个编译C/C++用的脚本,觉得好用的话把它保存起来加上可执行权限放到$PATH目录中去。
emacs虽然mode-cc很不错,可惜执行还得另开一个shell的window,不如用这个了。

#!/bin/bash #Copyright (C) 2008, WANG Cong #GPLv3 applies. if (( $# < 1)); then

        echo "Bad usage!"

        exit 1

fi FILENAME=$1 CC="gcc" CFLAGS="-Wall -W -Wshadow -Wpointer-arith -Wcast-qual -Wcast-align         -Wnested-externs -Waggregate-return -Wundef         -Wbad-function-cast -Wmissing-prototypes -Wstrict-prototypes         -Wmissing-declarations -Wconversion -Winline -Wformat-nonliteral         -Wformat-security -Wunknown-pragmas -Wredundant-decls         -std=c99 -s -g3 -O" CPPFLAGS="-Wall -W -Wshadow -std=c++98 -ffor-scope -Wpointer-arith -s -g3 -O" while [[ "$FILENAME" != "" ]] do

        OUTFILE=${FILENAME%.*}

        POSTFIX=${FILENAME##*.}

        if [ $OUTFILE = $FILENAME ] || [ $POSTFIX = $FILENAME ] || 

                [ -z $OUTFILE ] || [ -z $POSTFIX ];

        then

                echo "Bad file name!"

                exit 2

        fi

        if [[ "$POSTFIX" = "cpp" ]] || [[ "$POSTFIX" = "cxx" ]] || 

                [[ "$POSTFIX" = "cc" ]] ;

        then

                CC="g++"

                CFLAGS=$CPPFLAGS

        fi

        $CC $CFLAGS -o $OUTFILE $FILENAME

        if (($?!=0)); then

                exit 1

        fi

        echo "Result of exec $OUTFILE:"

        /bin/bash -c "./$OUTFILE"

        echo "End of $FILENAME"

        echo "========================"

        rm -f $OUTFILE

        shift

        FILENAME=$1

done exit 0

欣赏STL代码

无意间看到STL代码,忍不住读了一下,写得很简练,值得我们学习。在这里贴出来和大家分享一下。

最先看的是algorithm里的next_permutation的实现,非递归,代码很精炼,值得好好研究。

template
bool next_permutation(_BidirectionalIter first, _BidirectionalIter last)
{
// concept requirements
glibcpp_function_requires(BidirectionalIteratorConcept);
glibcpp_function_requires(LessThanComparableConcept<
typename iterator_traits::value_type>);

if (first == last)
return false;
_BidirectionalIter i = first;
++i;
if (
i == last)
return false;
i = last;
i;

for(;;) {
_BidirectionalIter ii = i;
i;
if (*
i < ii) {
_BidirectionalIter
j = __last;
while (!(
i < *—j))
{}
iter_swap(i, j);
reverse(ii, last);
return true;
}
if (i == first) {
reverse(first, last);
return false;
}
}
}

去重方法unique的实现:

template template
void list::unique(_BinaryPredicate binary_pred)
{
iterator
first = begin();
iterator last = end();
if (
first == last) return;
iterator
next = first;
while (++
next != last) {
if (
binary_pred(__first, next))
erase(
next);
else
first = next;
next = first;
}
}

看完了代码才想起来,使用unique的前提是list必须是有序的。

为了看后面的reverse方法,我们先看看它用到的transfer方法,这个一个很重要的方法,好几个方法都用到了它。transfer的作用是把[first, last)之间的元素都移动到position之前。

protected:
void transfer(iterator position, iterator first, iterator last) {
if (
position != last) {
// Remove [first, last) from its old position.
((_Node*) (
last._M_node->_M_prev))->_M_next = position._M_node;
((_Node*) (
first._M_node->_M_prev))->_M_next = last._M_node;
((_Node*) (
position._M_node->_M_prev))->_M_next = __first._M_node;

  // Splice [first, last) into its new position.
  _Node* __tmp = (_Node*) (__position._M_node-&gt;_M_prev);
  __position._M_node-&gt;_M_prev = __last._M_node-&gt;_M_prev;
  __last._M_node-&gt;_M_prev      = __first._M_node-&gt;_M_prev;
  __first._M_node-&gt;_M_prev    = __tmp;
}

}

然后reverse出场:

template
void list::reverse()
{
// Do nothing if the list has length 0 or 1.
if (_M_node->_M_next != _M_node &&
((_Node*) (_M_node->_M_next))->_M_next != _M_node) {
iterator first = begin();
++
first;
while (first != end()) {
iterator
old = first;
++
first;
transfer(begin(), old, first);
}
}
}

连接操作splice,这里看的这个splice是把list上的i移到position位置上。

void splice(iterator position, list&, iterator i) {
iterator j = i;
++j;
if (
position == i || position == j) return;
transfer(
position, i, j);
}

最后是sort方法,据说用了quick sort算法,不过还没看太懂……

template
void list::sort()
{
// Do nothing if the list has length 0 or 1.
if (_M_node->_M_next != _M_node &&
((_Node) (_M_node->_M_next))->_M_next != _M_node) {
list carry;
list
counter[64];
int fill = 0;
while (!empty()) {
carry.splice(__carry.begin(),
this, begin());
int i = 0;
while(
i < fill && !counter[i].empty()) { counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if (i == fill) ++__fill;
}

for (int __i = 1; __i &lt; __fill; ++__i)
  __counter[__i].merge(__counter[__i-1]);
swap(__counter[__fill-1]);

}
}

Linux下的反调试技术

作者:西邮 王聪

如何防止自己的程序被调试器跟踪,这是一个很有趣的话题,也是反逆向工程中的一个重要话题。这里简单介绍一下Linux平台上的反调试技术。

(本文主要参考:http://blog.txipinet.com/2006/10/05/37-tecnicas-anti-debugging-sencillas-para-gnu-linux/
做人要厚道,转载请指明出处!

一. int3指令

Intel Software Developer’s Manual Volume 2A中提到:

The INT 3 instruction generates a special one byte opcode (CC) that is intended for
calling the debug exception handler. (This one byte form is valuable because it can be
used to replace the first byte of any instruction with a breakpoint, including other one
byte instructions, without over-writing other code).

int3是一个特殊的中断指令(从名字上也看得出来),专门用来给调试器使用。这时,我们应该很容易想到,要反调试,只要插入int3来迷惑调试器即可。不过,这会不会影响正常的程序?会!因为int3会在用户空间产生SIGTRAP。没关系,我们只要忽略这个信号就可以了。

include

include

void handler(int signo)
{}

int main(void)
{
signal(SIGTRAP, handler);
asm(“nopnt”
“int3nt”);
printf(“Hello from main!n”);
return 0;
}

二. 文件描述符

这是一个很巧妙的办法,不过它只对gdb之类的调试器有效。方法如下:

include

include

include

int main(void)
{
if(close(3) == -1) {
printf(“OKn”);
} else {
printf(“traced!n”);
exit(-1);
}
return 0;
}

gdb要调试这个程序时会打开一个额外的文件描述符来读这个可执行文件,而这个程序正是利用了这个“弱点”。当然,你应该能猜到,这个技巧对strace是无效的。

三. 利用getppid

和上面一个手法类似,不过这个更高明,它利用getppid来进行探测。我们知道,在Linux上要跟踪一个程序,必须是它的父进程才能做到,因此,如果一个程序的父进程不是意料之中的bash等(而是gdb,strace之类的),那就说明它被跟踪了。程序代码如下:

include

include

include

include

include

include

include

int get_name_by_pid(pid_t pid, char* name)
{
int fd;
char buf[1024] = {0};
snprintf(buf, 1024, “/proc/%d/cmdline”, pid);
if ((fd = open(buf, O_RDONLY)) == -1)
return -1;
read(fd, buf, 1024);
strncpy(name, buf, 1023);
return 0;
}

int main(void)
{
char name[1024];
pid_t ppid = getppid();
printf(“getppid: %dn”, ppid);

    if (get_name_by_pid(ppid, name))
    return -1;
if (strcmp(name, "bash") == 0 ||
    strcmp(name, "init") == 0)
        printf("OK!n");
else if (strcmp(name, "gdb") == 0 ||
    strcmp(name, "strace") == 0 ||
    strcmp(name, "ltrace") == 0)
    printf("Traced!n");
else
    printf("Unknown! Maybe traced!n");

return 0;

}

同样的手法,一个更简单的方式是利用session id。我们知道,不论被跟踪与否,session id是不变的,而ppid会变!下面的程序就利用了这一点。

include

include

include

int main(void)
{
printf(“getsid: %dn”, getsid(getpid()));
printf(“getppid: %dn”, getppid());

    if (getsid(getpid()) != getppid()) {
    printf("traced!n");
    exit(EXIT_FAILURE);
}
    printf("OKn");

return 0;

}

四. 利用环境变量

bash有一个环境变量叫$_,它保存的是上一个执行的命令的最后一个参数。如果在被跟踪的状态下,这个变量的值是会发生变化的(为什么?)。下面列出了几种情况:


argv[0] getenv(“_”)
shell ./test ./test
strace ./test /usr/bin/strace
ltrace ./test /usr/bin/ltrace
gdb /home/user/test (NULL)

所以我们也可以据此来判断。

include

include

include

int main( int argc, char *argv[])
{
printf(“getenv(): %sn”, getenv(““));
printf(“argv[0]: %sn”, argv[0]);

if(strcmp(argv[0], (char *)getenv("_"))) {
    printf("traced!n");
    exit(-1);
}

printf("OKn");
    return 0;

}

五. 利用ptrace

很简单,如果被跟踪了还再调用ptrace(PTRACE_TRACEME…)自然会不成功。

include

include

int main(void)
{
if ( ptrace(PTRACE_TRACEME, 0, 1, 0) < 0 ) {
printf("traced!n");
return 1;
}
printf("OKn");
return 0;
}

Happy hacking!

还可以这样利用x86的堆栈

原来还能这样“践踏”x86的堆栈,利用push后直接ret,很简单很直接!以前都是利用缓冲区溢出去覆盖~

我写的用户空间的一段示例代码(注:执行时的段错误是意料之中的):

include

void hello(void)
{
printf(“hello world!n”);
}

void pushcall(void *call)
{
asm _volatile
(“pushl %%eaxnt”
“ret”
::”a” (call)
);
}

int main(void)
{
push_call(&hello);
return 0;
}