some interesting code

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example1:

1
2
3

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example2:

1
2

Input: "cbbd"
Output: "bb"

solution

Dynamic Programming

1
2
3
4
5
6
7
8

define P(i, j) = if S[i, j] is a palindrome ? true : false

Recursive:
P(i, j) = (P(i+1, j-1) and S[i] == S[j])

Base:
P(i,i) = true
P(i, i+1) = (S[i] == S[i+1])

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

class Solution {
    public:
    string longestPalindrome(string s) {
        int size = s.size();
        if (size < 2)
            return s;
        
        bool dp[size][size];
        
        int maxLen = 1;
        int pos = 0;
        
        for (int j = 0; j < size; ++j) {
            dp[j][j] = true;    
            for (int i = 0; i < j; ++i) {
                if (j == i+1) {
                    dp[i][j]= (s[i] == s[j]);
                } else {
                    dp[i][j] = ((s[i] == s[j]) && dp[i+1][j-1]);
                }
                int len = j - i + 1;
                if (len > maxLen && dp[i][j]) {
                    maxLen = len;
                    pos = i;
                }
            }
        }
        return s.substr(pos, maxLen);
    }
};

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

1
2

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

1
2

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

solution

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

class Solution {
public:
    template<typename Comparator>
    int partition(vector<int>& nums, int left, int right, Comparator cmp) {
        int pivot = nums[left];
        swap(nums[left], nums[right]);
        
        int pos = left;
        for (int i = left; i < right; ++i) {
            if (cmp(nums[i], pivot)) {
                swap(nums[i], nums[pos++]);
            }
        }
        swap(nums[pos], nums[right]);
        return pos;
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        
        int left = 0;
        int right = nums.size() - 1;
        
        while (left <= right) {
            int idx = partition(nums, left, right, greater<>());
            if (idx == k - 1)
                return nums[idx];
            else if (idx < k - 1)
                left = idx + 1;
            else
                right = idx - 1;
        }
        return -1;
    }
};

OR

1
2
3
4
5
6
7

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        nth_element(nums.begin(), nums.end()-k, nums.end());
        return nums[nums.size()-k];   
    }
};

show the basic approach in kernel pwn

host environment:

• Linux 4.19.102 x86_64
• gcc 9.2.0
• qemu 4.2.0
• busybox 1.31.1
• linux-5.5.2
  Read more »

进程

进程的状态

1. 运行态（占用CPU）
2. 就绪态（等待调度程序调度）
3. 阻塞态（等待阻塞原因解决）
   Read more »

bin地址

0x00问题所在

1. free后的堆指针没用置空
2. free没有对flag进行判断是否已经free过了

0x01unlink

• 发生在free一个chunk，发现相邻的chunk处于free状态，从bin双链表取出来的时候，合并至少两个free chunk。前一个chunk的状态通过p->presize的最低位来判断，后一个chunk的状态通过(p+p->size+(p+size)->size)->presize的最低位来判断。

  Read more »

pwnable

ssh [email protected] -p 2222 (password: guest)

设备：树莓派3B 系统：LEDE 4.4.92

1. 下载安装transmission-cli-openssl transmission-daemon-openssl transmission-remote-openssl transmission-web luci-app-transmission luci-i18n-transmission-zh-cn

2. 配置transmission

   直接在网页配置，或者使用配置文件/etc/config/transmisson

   Read more »

0x00概念

一个文件都有一个所有者, 表示该文件是谁创建的. 同时, 该文件还有一个组编号, 表示该文件所属的组, 一般为文件所有者所属的组. 如果是一个可执行文件, 那么在执行时, 一般该文件只拥有调用该文件的用户具有的权限. 而setuid, setgid 可以来改变这种设置.

setuid:该标志是让普通用户可以以root用户的角色运行只有root帐号才能运行的程序或命令。通过设置setuid权限位（也就是r-s--x--x中的s),使可执行程序暂时获得root权限,及程序涉及到的root操作能够进行.

this is a test, not true

0x00准备

• 本次实验的机器为Ubuntu 16.04.2 LTS64位系统

• 用gcc编译需要关闭stack-protector

• 需要gdb peda pwntools

  Read more »

this is a test not true

0x00准备

• 本次实验的机器为Ubuntu 16.04.2 LTS64位系统

• 需要关闭ASLR，echo 0 > /proc/sys/kernel/randomize_va_space，如果提示权限不够，可能需要用su提升权限

• 用gcc编译需要关闭stack-protector，打开NX

• 需要gdb peda python2 ROPgadget or Ropper

  Read more »

this is a test, not true

0x00准备

• 本次实验的机器为Ubuntu 16.04.2 LTS64位系统

• 需要关闭ASLR，echo 0 > /proc/sys/kernel/randomize_va_space，如果提示权限不够，可能需要用su提升权限

• 用gcc编译需要关闭stack-protector，允许栈的执行权限execstack

• 需要gdb peda python2

• 需要一串shellcode，本次使用

  \x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05

  Read more »