CS110L-Week 2 Exercises: Ownership and structs

第2周作业链接: https://reberhardt.com/cs110l/spring-2020/assignments/week-2-exercises/

本周将带你更加的熟悉Rust,包括所有权和引用等知识。

第一部分: 所有权


fn main()
{

    let mut s = String::from("hello");
    let ref1 = &s;
    let ref2 = &ref1;
    let ref3 = &ref2;

    //s = String::from("goodboy"); //错误 s

    println!("{}", ref3.to_uppercase());
}
fn drip_drop() -> String {

    let s = String::from("hello,world");
    
    //return &s; //错误

    return s;
}

    let s1 = String::from("hello");
    let mut v = Vec::new();
    v.push(s1);

    //let s2: String = v[0];  //错误

    let ref s2: String = v[0];
    println!("{}",s2);

第二部分:rdiff

我们将实现diff命令行实用程序的简单版本以比较两个文件。

代码:

第三部分 rwc

代码:

CS110L-Week 1 Exercises: Hello world

第一周作业链接: https://reberhardt.com/cs110l/spring-2020/assignments/week-1-exercises/

第一周的作业主要是熟悉Rust的工具链安装和一些Rust语法

第一部分 helloworld

安装工具链,访问Rust官方: https://www.rust-lang.org/tools/install

helloworld

cargo 提供了命令行来创建rust项目

cargo new helloworld

然后就可以cargo build 或者cargo run

➜  helloworld git:(main) ✗ tree
.
├── Cargo.lock
├── Cargo.toml
├── src
│   └── main.rs
└── target
    ├── CACHEDIR.TAG
    └── debug
        ├── build
        ├── deps
        │   ├── helloworld-681c2ade33f71cab
        │   └── helloworld-681c2ade33f71cab.d
        ├── examples
        ├── helloworld
        ├── helloworld.d
        └── incremental
            └── helloworld-3gmsxxterlir4
                ├── s-fw1pxstg53-1leo6ld-2439fudoc3hif
                │   ├── 14i0bcdbfi2ugad2.o
                │   ├── 15ne1gcrt9rvpglq.o
                │   ├── 18abmkatn3n4l0hu.o
                │   ├── 27s29o1kcsspusdg.o
                │   ├── 2xwm4i2jxgoiz5co.o
                │   ├── 3050lnwbirtj1yb5.o
                │   ├── dep-graph.bin
                │   ├── gp126zvew3eug9.o
                │   ├── q4wkdgq1k2s2v4m.o
                │   ├── query-cache.bin
                │   └── work-products.bin
                └── s-fw1pxstg53-1leo6ld.lock

从上面可以看到,整个项目的结构。src/main.rs 是源代码 target中的目录为编译生成的目录

main.rs 自带hello,world

fn main() {
    println!("Hello, world!");
}

Cargo.toml是包依赖

[package]
name = "helloworld"
version = "0.1.0"
authors = ["Jimmy Xiang <xxg1413@gmail.com>"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]

第二部分 Rust语法热身

    let n:i32 = 1;
    let n = 1;


    //可变类型
    let mut  n = 0;
    n = n + 1;

    //Rust有两种字符串: &str和String
    let s: &str = "hello,world"; //只读数据段

    let mut s: String = String::from("hello,");
    s.push_str("world");
    println!("{}", s);


     //动态数组
     let mut v: Vec<i32> = Vec::new();
     v.push(2);
     v.push(3);

     
     //固定大小数组
     let mut arr: [i32; 4] = [0,2,4,8];
     arr[0] = -2;
     println!("{}", arr[0]+arr[1]);


     //迭代器
     for i in arr.iter()
     {
         println!("{}",i);
     }


     //while
    let mut sum = 0;
    let mut i = 0;
     while i < 20 
     {
         i += 1;
         sum += i;

     }

     println!("sum={}",sum);


    //loop  它有助于编译器对变量初始化进行一些假设。
    let mut i = 0;
    loop {

        i += 1;

        if i == 10 {
            break;
        }
    }

    println!("i={}",i);

    //函数

    fn mysum(a: i32, b:i32) -> i32 
    {
        a + b  //Rust是一种基于表达式的 语言,不需要分号

        //a + b ; 会出错
    }
     
    println!("sum={}", mysum(1,2));

练习:

use std::collections::HashSet;
//练习

fn add_n(v: Vec<i32>, n: i32) -> Vec<i32> {
    

    let mut result: Vec<i32> = Vec::new();

    for i in v.iter() {
        result.push(i+n)
    }

    result
}

fn add_n_inplace(v: &mut Vec<i32>, n: i32) {

    let mut i = 0;

    while i < v.len() {

        v[i] = v[i] + n;
        i = i + 1;
    }
}

fn dedup(v: &mut Vec<i32>) {


    let mut hs = HashSet::new();
    let mut i = 0;

    while i < v.len() {

        if !hs.contains(&v[i]) {

            hs.insert(v[i]);
            i += 1;

        }  else {

            v.remove(i);
        }
    
    }
}



#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_add_n() {
        assert_eq!(add_n(vec![1], 2), vec![3]);
    }

    #[test]
    fn test_add_n_inplace() {
        let mut v = vec![1];
        add_n_inplace(&mut v, 2);
        assert_eq!(v, vec![3]);
    }

    #[test]
    fn test_dedup() {
        let mut v = vec![3, 1, 0, 1, 4, 4];
        dedup(&mut v);
        assert_eq!(v, vec![3, 1, 0, 4]);
    }
}

第三部分 Hangman

代码: https://github.com/xxg1413/CS110L/tree/main/Assignments/week1/Hangman

CS110L-#02: Memory Safety

课程总目录: https://github.com/xxg1413/CS110L

第二节 Memory Safety

视频:

Youtube:https://www.youtube.com/watch?v=cUrggIAPJEs&feature=youtu.be

Slides:https://reberhardt.com/cs110l/spring-2020/slides/lecture-02.pdf

课程笔记:https://reberhardt.com/cs110l/spring-2020/lecture-notes/lecture-02/

B站中字:https://www.bilibili.com/video/BV1Ra411A7kN?p=2

笔记

0.上节课的练习的答案

解释:https://stanford-cs242.github.io/f19/lectures/06-2-memory-safety

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// There are at least 7 bugs relating to memory on this snippet.
// Find them all!

// Vec is short for "vector", a common term for a resizable array.
// For simplicity, our vector type can only hold ints.
typedef struct {
  int* data;     // Pointer to our array on the heap
  int  length;   // How many elements are in our array
  int  capacity; // How many elements our array can hold
} Vec;

Vec* vec_new() {
  Vec vec; //本地变量
  vec.data = NULL;
  vec.length = 0;
  vec.capacity = 0;
  return &vec;  //悬浮指针
}

void vec_push(Vec* vec, int n) {
  if (vec->length == vec->capacity) {
    int new_capacity = vec->capacity * 2;
    int* new_data = (int*) malloc(new_capacity);
    assert(new_data != NULL);

    for (int i = 0; i < vec->length; ++i) {
      new_data[i] = vec->data[i];
    }

    vec->data = new_data; //忘记释放内存 内存泄露
    vec->capacity = new_capacity;
  }

  vec->data[vec->length] = n; //指针的值改变了 n就改变了
  ++vec->length;
}

void vec_free(Vec* vec) {
  free(vec);
  free(vec->data);
}

void main() {
  Vec* vec = vec_new();
  vec_push(vec, 107);

  int* n = &vec->data[0];
  vec_push(vec, 110);
  printf("%d\n", *n);//*n 迭代失效

  free(vec->data);
  vec_free(vec);// 双重释放
}

1.Rust编写bug的一些问题

Rust只是比其他语言犯错更难一些,并不代表不可以犯错。而且很多逻辑错误是无关语言的。

2.Rust编译器

3.Rust所有权

4.Rust的借用

5.生命周期

资源:

https://stanford-cs242.github.io/f19/lectures/06-2-memory-safety

CS110L-#01: Welcome to CS 110L

第一节 Welcome to CS 110L

视频:

Slides:https://reberhardt.com/cs110l/spring-2020/slides/lecture-01.pdf

笔记

1.为什么使用Rust

2.为什么不是用C/C++?

安全问题:

例子程序:https://www.tutorialspoint.com/convert-a-string-to-uppercase-in-c

看了一下,程序的作用是把字符串转成大写,明显gets存在缓冲区溢出。在编译的时候,编译器也提醒了。

➜  01 git:(main) ✗ ./a.out 

Enter a string:ashdasihdddddddddddddddddddddddddddddddddddddddddddddddddddddddd

String in Upper Case = ASHDASIHDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD%                                              
➜  01 git:(main) ✗ ./a.out

Enter a string:GgaudiasSSSSSSSSSASUGDAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

*** stack smashing detected ***: terminated
[1]    18336 abort      ./a.out

很明显,C/C++的内存安全的问题很严重,这其实也是众所周知的,老师还提到一篇论文,关于汽车攻击面的。

论文:http://www.autosec.org/pubs/cars-usenixsec2011.pdf

YouTube解读: https://www.youtube.com/watch?v=bHfOziIwXic

还提到Chrome OS中的一个 one byte overflow and symlinks,DNS库的一个字节的溢出

链接: https://googleprojectzero.blogspot.com/2016/12/chrome-os-exploit-one-byte-overflow-and.html

然后老师讨论缓冲区溢出的问题,举了一个例子:

char buffer[128];
int bytesToCopy = packet.length;
if (bytesToCopy < 128) {
 strncpy(buffer, packet.data, bytesToCopy);
}

看起来是有边界检查的,也使用了带有长度的strncpy函数。但是其实strncpy也是有问题的,容易产生空字符结尾错误和其他的问题。

但是这里的问题,其实是整数转换的问题。

C/C++的内存安全问题,也有很多人搞了一些工具来检查。主要是动态分析和静态分析,动态分析需要预测输入,静态分析主要是错误非常多。

比如: valgrind

我用valgrind来跑convert程序,看看会出什么样的结果

➜  01 git:(main) ✗ valgrind --tool=memcheck --leak-check=full ./conver
==2022== Memcheck, a memory error detector
==2022== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2022== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
==2022== Command: ./conver
==2022==

Enter a string:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

*** stack smashing detected ***: terminated
==2022==
==2022== Process terminating with default action of signal 6 (SIGABRT)
==2022==    at 0x489C18B: raise (raise.c:51)
==2022==    by 0x487B858: abort (abort.c:79)
==2022==    by 0x48E63ED: __libc_message (libc_fatal.c:155)
==2022==    by 0x4988B49: __fortify_fail (fortify_fail.c:26)
==2022==    by 0x4988B15: __stack_chk_fail (stack_chk_fail.c:24)
==2022==    by 0x109245: main (convert.c:22)
String in Upper Case = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA==2022==
==2022== HEAP SUMMARY:
==2022==     in use at exit: 0 bytes in 0 blocks
==2022==   total heap usage: 2 allocs, 2 frees, 2,048 bytes allocated
==2022==
==2022== All heap blocks were freed -- no leaks are possible
==2022==
==2022== For lists of detected and suppressed errors, rerun with: -s
==2022== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
[1]    2022 abort      valgrind --tool=memcheck --leak-check=full ./conver

其实valgrind检查不了这种缓冲区溢出的漏洞。

3.为什么不是用其他有GC的语言?

GC 有性能问题,垃圾一般都是丢在你家里,收集垃圾的需要敲你的门来收集垃圾。

  • 代价昂贵
  • 具有破坏性
  • 存在非确定性
  • 排除了手动优化的可能

需要程序都需要高性能,比如

  • 用户界面程序
  • 游戏
  • 自动驾驶
  • 支付处理
  • 高频交易

4.预习

找bug,链接: https://web.stanford.edu/class/cs110l/lecture-notes/lecture-02/

解答:

程序如下

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// There are at least 7 bugs relating to memory on this snippet.
// Find them all!

// Vec is short for "vector", a common term for a resizable array.
// For simplicity, our vector type can only hold ints.
typedef struct {
  int* data;     // Pointer to our array on the heap
  int  length;   // How many elements are in our array
  int  capacity; // How many elements our array can hold
} Vec;

Vec* vec_new() {
  Vec vec;
  vec.data = NULL;
  vec.length = 0;
  vec.capacity = 0;
  return &vec;
}

void vec_push(Vec* vec, int n) {
  if (vec->length == vec->capacity) {
    int new_capacity = vec->capacity * 2;
    int* new_data = (int*) malloc(new_capacity);
    assert(new_data != NULL);

    for (int i = 0; i < vec->length; ++i) {
      new_data[i] = vec->data[i];
    }

    vec->data = new_data;
    vec->capacity = new_capacity;
  }

  vec->data[vec->length] = n;
  ++vec->length;
}

void vec_free(Vec* vec) {
  free(vec);
  free(vec->data);
}

void main() {
  Vec* vec = vec_new();
  vec_push(vec, 107);

  int* n = &vec->data[0];
  vec_push(vec, 110);
  printf("%d\n", *n);

  free(vec->data);
  vec_free(vec);
}

运行:

[1] 4278 segmentation fault ./pre

直接段错误

7处错误:

  1. 在vec_new中,创建了一个局部变量vec,并返回了&vec
  2. vec.data 应该是vec->data = NULL
  3. vec_push中不要使用assert
  4. vec_push中vec->length没有检查,而且可以设置为unsigned
  5. free(vec->data)错误
  6. vec_free中应该先free(vec->data)
  7. vec_push 中 ++vec->length错误

第一周的作业

作业链接:

[rust-ctf] VolgaCTF 2017 Quals: Transformer

VolgaCTF 2017 Quals: Transformer

链接: https://ctftime.org/task/3695

题目:transformer

We’ve got a file that was processed with a binary called transformer. We really need the contents of this file. Can you help?


开始探索

在Mac上执行程序:


[Transformer] ./transformer zsh: exec format error: ./transformer


使用file 查看 文件属性
[Transformer] file transformer transformer: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=3ba9baed5d1738eef040f333ec9c4707c3aeabf4, with debug_info, not stripped


发现是 64 位 Linux 二进制文件,拿到Linux系统下运行

➜ Transformer git:(main) ✗ ./transformer Usage: transformer <input_file> <output_file>

使用ldd 看看调用的库
➜ Transformer git:(main) ✗ ldd ./transformer linux-vdso.so.1 (0x00007ffc0c1ed000) libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007fdccaf82000) librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x00007fdccaf77000) libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007fdccaf55000) libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007fdccaf3b000) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fdccad76000) /lib64/ld-linux-x86-64.so.2 (0x00007fdccb1f5000)

我们尝试调用一下这个程序,构造一个输入文件:


➜ Transformer git:(main) ✗ ./transformer input.txt output.txt ➜ Transformer git:(main) ✗ cat input.txt output.txt 123456 uV���7�#


123456 输入,输出的内容看不懂,有乱码, 文件类型为data,文件大小由7 bit变成了12 bit

用IDA打开二进制文件