ARTS-week17

发表于 2018-11-25 分类于 ARTS 本文字数： 3.6k 阅读时长 ≈ 3 分钟

Algorithms

Convert Sorted Array to Binary Search Tree

思路: 二分查找树，使中间元素为根，然后递归构造左右子树。用二叉树递归的方法实现，以根作为返回值，每层递归函数取中间元素，作为当前根和赋上结点值，然后左右结点接上左右区间的递归函数返回值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        return ArrayToBST(num, 0 , num.size() - 1);
    }
    TreeNode *ArrayToBST(vector<int> &num, int left, int right) {
         if (left > right) {
            return NULL;
        }
        int mid = (left + right) / 2;
        TreeNode *root = new TreeNode(num[mid]);
        root->left = ArrayToBST(num, left, mid - 1);
        root->right = ArrayToBST(num, mid + 1, right);
        return root;
    }
};

Convert Sorted List to Binary Search Tree

思路: 仍然使用二叉树递归的方式，但是和Array不同，链表不能直接访问任意元素。那么在链表中找到中间节点作为当前根节点，可以使用快慢指针的方式，快指针每次走两步，慢指针每次走一步，当快指针走到结尾时，那么慢指针就是中间节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        if (head == NULL) {
            return NULL;
        }
        return ListToBST(head, NULL);
    }

    TreeNode* ListToBST(ListNode* head, ListNode* tail) {
        if(head == tail) {
            return NULL;
        }

        ListNode* fast = head;
        ListNode* slow = head;

        while(fast != tail && fast->next != tail) {
            slow = slow->next;
            fast = fast->next->next;
        }

        TreeNode* node = new TreeNode(slow->val);
        node->left = ListToBST(head, slow);
        node->right = ListToBST(slow->next, tail);

        return node;
    }
};

Review

本周阅读英文文章 10 Bad Habits To Avoid As A Developer

Technique

在阅读《Linux/UNIX系统编程手册》时，学习到了关于-fPIC的知识点。首先创建一个共享库，将编译源代码文件和创建共享库放在一个命令中执行:

1	gcc -g -fPIC -Wall mod1.c mod2.c mod3.c -shared -o libfoo.so

cc-fPIC选项指定编译器应该生成位置独立的代码，这会改变编译器生成执行特定操作的代码的方式，包括访问全局、静态和外部变量，访问字符串常量，以及获取函数的地址。这些变更使得代码可以在运行时被放置在任意一个虚拟地址处。

确定一个既有目标文件在编译时是否使用了-fPIC选项，可以使用下面两个命令中的一个来检查目标文件符号表中是否存在名称_GLOBAL_OFFSET_TABLE_。

1 2	$ nm mod1.o \| grep _GLOBAL_OFFSET_TABLE_ 00000000002d9000 d _GLOBAL_OFFSET_TABLE_

1 2	$ readelf -s mod1.o \| grep _GLOBAL_OFFSET_TABLE_ 434: 00000000002d9000 0 OBJECT LOCAL DEFAULT 23 _GLOBAL_OFFSET_TABLE_

相应地，如果下面两个相互等价的命令中的任意一个产生了任何输出，那么指定的共享库中至少有一个目标模块在编译时没有指定-fPIC选项。

1 2	$ objdump --all-headers libfoo.so \| grep TEXTREL $ readelf -d libfoo.so \| grep TEXTREL

字符串TEXTREL表示存在一个目标模块，其文本段中包含需要运行时重定位的引用。
其中objdump命令可以用来获取各类信息——反汇编的二进制机器码——从一个可执行文件、编译过的目标以及共享库中。它还能够用来显示这些文件各个ELF节的头部信息。

nm命令会列出目标库或可执行程序中的一组符号。这个命令的用途是找出哪些库定义了一个符号。例如

$ nm -A /lib/x86_64-linux-gnu/libpthread*.so | grep 'pthread_mutex_init'
/lib/x86_64-linux-gnu/libpthread-2.23.so:00000000000095a0 t __GI___pthread_mutex_init
/lib/x86_64-linux-gnu/libpthread-2.23.so:00000000000095a0 T __pthread_mutex_init
/lib/x86_64-linux-gnu/libpthread-2.23.so:00000000000095a0 T pthread_mutex_init

本周阅读《HTTPS权威指南：在服务器和Web应用上部署SSL/TLS和PKI》一书时学习到的知识点:
一、协议降级攻击
协议降级攻击是指攻击者作为中间人企图修改TLS握手过程中的连接参数。具体思路是，攻击者希望迫使握手使用一个低等级的协议或者使用低强度的密码套件。在SSL 2中，这类攻击是很容易发生的，因为该协议不提供握手的完整性校验。后续的SSL协议则提供握手完整性校验以及其他的附加手段来检测类似的攻击。然而，协议设计者没有想到的是由协议演进而带来的协议互操作性问题。浏览器会尽最大可能与所有服务器进行通信。不幸的是，在TLS协议上，这种尝试会导致安全风险，因为浏览器为了兼容服务器，会降低它们的安全能力，也就是为了互操作性而降低安全性。

二、自愿协议降级
当互操作性问题出现之后，浏览器开始支持自愿协议降级（voluntary protocol downgrade）。具体来说就是首先使用其支持的最高TLS版本尝试连接，并启用所有支持的选项和扩展。如果首次尝试连接失败，则减少选项并降低协议版本；浏览器会持续进行这种尝试直到连接建立。例如，当TLS 1.0协议为最高版本的时候，自愿协议降级在最坏的情况下会尝试2次，而对于TLS 1.2，则会尝试3~4次。

注意: 互操作性问题不仅仅是导致TLS握手失败的原因。有充足的证据表明代理服务器、防火墙以及杀毒软件经常基于协议版本号和其他的握手属性来拦截和过滤连接。

Algorithms

Review

Technique

Share