并查集算法学习

蓝桥杯题目:合根植物

问题描述

w星球的一个种植园,被分成 m * n 个小格子(东西方向m行,南北方向n列)。每个格子里种了一株合根植物。
这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?

输出格式

第一行,两个整数m,n,用空格分开,表示格子的行数、列数(1<m,n<1000)。
接下来一行,一个整数k,表示下面还有k行数据(0<k<100000)
接下来k行,第行两个整数a,b,表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行,从上到下,从左到右编号。
比如:5 * 4 的小格子,编号:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

样例输出

1
5

其和根情况如下图

一直把6这个点给忽略了,6也可以算一个根。

解决方案

这里采用并查集算法。

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
#include <stdio.h>
#include <string.h>
int* all;
int count = 0 ;

void union1(int a, int b){
all[b]=a;
}

int find(int a){
if(all[a]==0) return a;
all[a] = find(all[a]);
return all[a];

}
void func(int a , int b){

int ra = find(a);
int rb = find(b);
if(ra==rb) return ;
union1(ra,rb);
count ++;

}
int main(int argc, char *argv[]) {
int n = 0, m = 0,sum = 0, a = 0, b = 0;
scanf("%d%d",&m,&n);
scanf("%d",&sum);
all = new int[n*m + 1];
memset(all,0,(m*n+1)*sizeof(int));
for(int i = 0; i < sum ; i ++){
scanf("%d%d",&a,&b);
func(a,b);
}
printf("%d",m*n-count);
return 0;
}

就是把相同的两个点连接起来,最后分成多少个分组,这里使用的是并查集算法,百度有并查集算法的解释,这里只贴出这个例子

Windows 驱动入门

Windows驱动层是我一直想学的东西,最近也在看软件调试。

如果不了解驱动层的开发,就很难把驱动层的逆向学好。

目标很简单,先把驱动的基本安装代码实现,再把R0层与R3层通信的方式实现

最后通过R3层的程序能通过直接调用R0层的接口来实现R3层操作R0层。

DbgView配置

涉及到开发DbgView是必不可少的一个工具

windows7需要添加一个注册表项才能接受到DbgView的消息:

1
2
3
4
Windows Registry Editor Version 5.00

[HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Control\Session Manager]
"Debug Print Filter"=dword:0000000f

配置好后重启即可。

WDK + VS2012

这里用VS2012是因为win10对驱动开发不友好,选择Windows7做开发环境,VS2010代码提示有点问题,上次学C++开发CLR程序的时候根本没提示。

因此选用了VS2012,目前用的蛮好,现在我的开发环境一直用VS2012,那么WDK只能选择8.0了,8.1版本的WDK没办法支持VS2012。

还有我比较喜欢本地版本的MSDN,不想在WEB上查询代码,这些VS2012都能搞定,给大家推荐一下。

最简单的驱动程序

开发驱动,也是要从Hello,world开始入门的,这就来写一个最简单的驱动程序。

选用WDM空项目

上MSDN,找DriverEntry的代码,拷贝复制

编写一段入门程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <ntddk.h>

DRIVER_UNLOAD Unload;

NTSTATUS DriverEntry(PDRIVER_OBJECT DriverObject,PUNICODE_STRING RegistryPath){

DbgPrint("驱动加载成功!");

DriverObject->DriverUnload = Unload;


return STATUS_SUCCESS;
}


VOID Unload(struct _DRIVER_OBJECT *DriverObject){
DbgPrint("驱动卸载成功!");

}

将警告视为错误 这个选项禁用

编译成功,驱动成功被注册。

使用DbgView查看输出

第一步:打开选项

第二步:安装启动卸载驱动

总结一下,就是驱动要有个入口,类似于exe程序的main,然后入口的第一个参数是一个引用,你需要将引用的卸载地址指向卸载驱动的函数地址。

至此,HelloWorld之路已经走完了,下面要开始学习关于通信的方式了。

DriverEntry特性

DriverEntry()一共有 2 个参数

  • PDRIVER_OBJECT DriverObject,指向驱动程序对象的指针。
  • PUNICODE_STRING RegistryPath,驱动程序的服务主键,在DriverEntry() 返回后则会释放,需要用时记得保存。

在DriverEntry中,一般需要做一下几件事情:

  • 设置驱动卸载例程
  • 注册 IRP 的派遣函数
  • 创建设备对象

驱动卸载例程与 IRP 派遣函数都是对驱动对象设置的。

驱动通信的方式有很多:

  • 共享内存
  • 共享事件
  • IOCTL宏
  • ReadFile() 或 WriteFile()

今天这里学习的使用IOCTL宏来进行通信。

Win32程序使用 DeviceIoControl() 与驱动进行通信。

驱动程序与 I/O 管理器通信,使用的是 IRP,即 I/O 请求包。

IRP 分为2部分:

  • IRP 首部
  • IRP堆栈。

在驱动程序中,IRP 派遣例程几乎都有对应的 Win32 API 函数,下面介绍IRP派遣例程。

名称 描述 调用者
IRP_MJ_CREATE 请求一个句柄 CreateFile
IRP_MJ_CLEANUP 在关闭句柄时取消悬挂的IRP CloseHandle
IRP_MJ_CLOSE 关闭句柄 CloseHandle
IRP_MJ_READ 从设备得到数据 ReadFile
IRP_MJ_WRITE 传送数据到设备 WriteFile
IRP_MJ_DEVICE_CONTROL 控制操作(利用IOCTL宏) DeviceIoControl
IRP_MJ_INTERNAL_DEVICE_CONTROL 控制操作(只能被内核调用) N/A
IRP_MJ_QUERY_INFORMATION 得到文件的长度 GetFileSize
IRP_MJ_SET_INFORMATION 设置文件的长度 SetFileSize
IRP_MJ_FLUSH_BUFFERS 写输出缓冲区或丢弃输入缓冲区 FlushFileBuffers\FlushConsoleInputBuffer \PurgeComm
IRP_MJ_SHUTDOWN 系统关闭 InitiateSystemShutdown

IRP(I/O Request Package)

Ring3(用户层)应用程序调用kernel32.dll导出的DeviceIoControl函数后,会调用到ntdll.dll导出的NtDeviceIoControlFile函数,进而调用到ntoskrnl.exe提供的服务函数NtDeviceIo ControlFile,该函数会将I/O请求转化为IRP包,并发送到对应驱动的派遣例程函数中,其机制类似于Windows的消息机制。

IRP是一个很复杂的数据结构,IRP两个基本的属性:

  • MajorFunction
  • MinorFunction

分别记录IRP的主类型和子类型。

操作系统根据MajorFunction将IRP 分发给派遣函数,在派遣函数中还可以判断IRP属于哪种MinorFunction。

DriverEntry有个函数指针数组MajorFunction.都是派遣函数地址。

WinDbg调试指令

dt 指令,用于打印数据结构 举例 dt _PEB
x 指令,查找全局函数或变量,需要PDB支持 举例 x calc!g*
.reload 重载符号表
dd 32位数据显示 dq 64位数据显示
u 反汇编,u 00401000 返汇编目标地址
.formats 将虚拟地址转为二进制,用于分页机制中查找其内存地址
!process 0 0 命令列出所有进程

软件调试

CPU 基础

CPU的操作模式

保护模式和实模式

保护模式指的是具有强大的虚拟内存支持和完善的任务保护机制,实模式是直接操作物理IO地址。虚拟8086模式即保护模式下的类实模式。

寄存器

寄存器相关的逆向工程核心原理已介绍

特权级

描述符特权级 : Descriptor Privilege Level 简称DPL,位于段描述符或门描述符中,用于表示一个段或门的特权级别

PE文件结构学习总结

之前是基于数据来学习PE结构,学习的是PE结构的基础,但为了快速开发,应该使用winnt中提供的结构体来实现基于PE结构的相关功能,如内存载入DLL,内存注入,IAT HOOK等技术。

从文件头开始,即 0x0这个地址开始,遇到的会是一个DOS头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct _IMAGE_DOS_HEADER {      // DOS .EXE header
    WORD   e_magic;                     // Magic number
    WORD   e_cblp;                      // Bytes on last page of file
    WORD   e_cp;                        // Pages in file
    WORD   e_crlc;                      // Relocations
    WORD   e_cparhdr;                   // Size of header in paragraphs
    WORD   e_minalloc;                  // Minimum extra paragraphs needed
    WORD   e_maxalloc;                  // Maximum extra paragraphs needed
    WORD   e_ss;                        // Initial (relative) SS value
    WORD   e_sp;                        // Initial SP value
    WORD   e_csum;                      // Checksum
    WORD   e_ip;                        // Initial IP value
    WORD   e_cs;                        // Initial (relative) CS value
    WORD   e_lfarlc;                    // File address of relocation table
    WORD   e_ovno;                      // Overlay number
    WORD   e_res[4];                    // Reserved words
    WORD   e_oemid;                     // OEM identifier (for e_oeminfo)
    WORD   e_oeminfo;                   // OEM information; e_oemid specific
    WORD   e_res2[10];                  // Reserved words
    LONG   e_lfanew;                    // File address of new exe header
  } IMAGE_DOS_HEADER, *PIMAGE_DOS_HEADER;

逆向工程核心原理

第一章 软件逆向工程

软件逆向分析的2种方法:

1.静态分析

该方法主要使用IDA PRO等工具,对软件进行静态分析,整理软件分支结构,从而判断出软件的真正意图。

该方法适合简单应用程序以及未对代码进行保护的程序,通常加壳程序需要先对其进行脱壳才可使用IDA PRO 进行分析。

2.动态分析

该方法使用Ollydbg工具进行动态调试,使用Ollydbg进行动态调试时需要对PE文件结构,TSL回调函数,软件执行流程等有一点的认知

软件逆向工程中需要的基础知识:

1.C/C++代码知识
2.十六/二进制思维
3.汇编语言基础
4.操作系统知识

第二章 使用两种方式打补丁

1.通过直接在内存中修改

在内存中修改字符创后,重新生成PE文件,该方法局限于源字符串大小。

第三章 小端标记法

大端标记法常出现在底层,unix系统和网络协议大多使用大端标记法

小段标记法在windows和linux中被使用

小端的特点是高位放在高地址,低位放在低地址

大端的特点就是存储时像字符串一样

内存中的数据大多以4K对其方式

第四章 寄存器

X86体系结构计算机通常有如下寄存器:

8个通用寄存器 : eax ebx ecx edx esi edi esp ebp
6个段寄存器: cs ds ss es fs gs
一个状态/控制寄存器: eflags
一个程序指针寄存器: eip

eax常用于结果返回,edx通常协助eax进行计算
ebx用于地址计算
ecx用于累加
esi edi 用于数据传输
esp 堆栈当前地址
ebp 堆栈参考指针
cs 代码段
ds 数据段
ss 堆栈段
es 拓展数据段
fs gs 拓展数据段(有用的数据)

程序调试常用到FS寄存器,用于计算SEH 结构化异常处理机制,TEB 线程环境块 ,PEB 进程环境块等地址,属于高级调试必备的数据。

还有CR0-CR4 折4个控制寄存器,学习到了再讨论

第五章 栈

先进先出

第七章 栈帧

EBP保存当前栈空间位置,退出函数还原,即栈帧的概念

第八章 VB程序

消息框函数 rtcMsgBox

第十章 函数调用约定

cdecl 调用方式,调用者负责处理堆栈平衡,add esp,8
stdcall 调用方式,被调用者自行处理堆栈,return 8
fastcall 调用方式,与stdcall类似,但是会用到寄存器

第十三章 PE文件结构

用010 editor观察即可,最难的是导入表和导出表这部分

导出表 由 导出表的数据目录指向,数据目录指向的导出表地址是个链表,直到00000000结束

数据内容为一个结构一,其中有OriginalFirstThunk 和 FirstThunk 2个指针,指向一个指针数字

1数组指向需要的dll函数名
2在执行的时候,会把DLL文件中函数名的覆盖地址到该指针数组,但是未执行时该数组和1数组内容相同

第二十一章 DLL注入之Windows消息钩子

HOOK消息钩子,实现DLL注入。

第二十三章 DLL注入

方法:
1.线程注入DLL
2.注册表注入DLL
3.HOOK注入DLL
4.输入法注入DLL
5.导入表注入
6.内存注入/代码注入

第二十九章 API钩取技术(HOOK)

第三十七章 X64函数调用约定

X64中统一采用fastcall方式来调用

参数1 放在rcx XMM0
参数2 放在rdx XMM1
参数3 放在r8 XMM2
参数4 放在r9 XMM3

减少 push的使用 用move 传递参数,直接使用rsp进行堆栈操作

C++反汇编与逆向分析实战

今天开始学习这本书,做一些笔记,之前有一些基础,理解的部分便少做些记录了。

IDA Pro 常用快捷键

快捷键 功能
A 结实光标的地址为一个字符的首地址
B 十六进制和二进制进行转换
C 解释光标处地址为一条指令
D 解释光标为止为数据
G 快速查找大对应地址
H 十六进制和十进制转换
K 将数据解释为栈变量
; 添加注释
M 解释为枚举成员
N 重新命名
O 解释数据为一个数据读研偏移量
T 解释数据为一个结构体成员
X 切换师徒到交叉参考模式
Shift +F9 添加结构体

利用python连接并控制SSH

使用pexpect来连接ssh

(该工具只能在linux下使用)

python连接ssh并且执行命令,显示输出结果

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
#!/usr/bin/python
import pexpect
PROMPT = ['# ','>>> ','> ','\$ ']
def send_command(child,cmd):
child.sendline(cmd)
child.expect(PROMPT)
print child.before

def connect(user,host,password):
ssh_newkey = 'Are you sure you want to continue connecting (yes/no)?'
connStr = 'ssh ' + user + '@' + host
child = pexpect.spawn(connStr)
ret = child.expect([pexpect.TIMEOUT,ssh_newkey,'[P|p]assword: '])
if ret == 0:
print '[-] Error Connecting'
return
if ret ==1:
print "send yes to server!\n"
child.sendline('yes')
ret = child.expect([pexpect.TIMEOUT,'[P|p]assword: '])
if ret == 0:
print '[-] Error Connecting'
return
child.sendline(password)
child.expect(PROMPT)
return child
ss = connect("root","heiyiren.top","heiyiren312429020!@#")
send_command(ss,'cat /etc/shadow | grep root')

CloudStack安装部署

整整折腾了一个星期,终于将CloudStack的安装部署搞定了

整个流程下来遇到很多问题,也学到很多东西,果然遇到问题还是不要逃避才能学到知识。

对其进行二次开发做虚拟化的想法萌生出来,感觉这种方式来尽心信息安全实验开发环境开发是一件很有意义的事情。

有时间重新部署一遍,然后把过程记录下来,二次开发的话暂时不考虑,得等软件逆向这块知识啃下来之后再考虑,学校的事情也比较多,毕业设计也还没做!!!

python之端口扫描

使用python脚本进行tcp全连接测试

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
from socket import *
from threading import Thread
import optparse

def connPort(ipAddr,port):
setdefaulttimeout(1)
try:
conn = socket(AF_INET,SOCK_STREAM)
conn.connect((ipAddr,port))
conn.send(b"python\r\n")
print("[+] %d/tcp open"%port)
results = conn.recv(100)

print("[+] %s"%str(results,encoding="utf-8"))
except Exception as e:
#print(e)
pass

if __name__ == "__main__":
parser = optparse.OptionParser("python portscan.py -H <host ip addr> -p <port>")
parser.add_option("-H",dest='hAddr',type='string',help='specify ip addr')
parser.add_option("-p",dest='port',type='string',help='specify port')
(options,args) = parser.parse_args()
if options.hAddr==None or options.port==None:
print(parser.usage)
else:
ports = str(options.port).split(",")
for i in ports:
t = Thread(target=connPort,args=(options.hAddr,int(i)))
t.start()