XDP实现DNS Query Name Blacklist Filter（二）

实现公共模式提取算法

思路：

针对后缀固定，前面随机的：按每级域名处理（点分隔），TLD后缀单独处理。计算出每个后缀的频率之后，如有一个远高于第二，则认为它是攻击域名，生成程序屏蔽该后缀。

#include <map>
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <fstream>

#define simple_print(p) std::cout<<(p)<<std::endl

std::set<std::string> tldset = {"com", "net", "org", "gov", "edu", "cn", "uk", "us", "ru"};

bool is_suffix(std::string base, std::string suf){
    if(base.length() < suf.length())
        return false;
    int diff = base.length() - suf.length();
    for(int i=suf.length()-1;i>=0;--i){
        if(base[i+diff] != suf[i])
            return false;
    }
    return true;
}

void domain2qname(char *domain, int len){
	if(len > 253)
		return;
	
    int i=0;
    for(;i<len;++i){
        if(domain[i] == '.'){
            int j;
            for(j=i+1;j<len;++j){
                if(domain[j] == '.'){
                    break;
                }
            }
            domain[i] = j-i-1+'0';
            i=j-1;
        }
    }
}

int main(int argc, char **argv){
    // if(argc != 2){
    //     std::cout << "Wrong arg" << std::endl;
    //     return 1;
    // }
    // std::string fname = std::string(argv[1]);
    
    std::map<std::string, int> sufmap;
    char dmbuf[256];

    std::ifstream in("domains.t");
    if(!in.is_open()){
        std::cout << "File error" << std::endl;
        return 1;
    }

    int i, last, cnt;
    int dmlens[20];
    //将各个后缀存入map计数
    while(in.getline(dmbuf, 255)){
        memset(dmlens, 0, sizeof(dmlens));
        for(i=0,last=-1,cnt=0;i<256&&dmbuf[i];++i){
            if(dmbuf[i] == '.'){
                dmlens[cnt++] = i-last;
                last = i;
            }
        }
        while(cnt--){
            std::string suffix(dmbuf+last+1);
            sufmap[suffix]++;
            last -= dmlens[cnt];
        }
    }

    //计算出现频率，并比较大小
    int max=0, sec=0;
    std::map<std::string, int>::iterator iter, maxiter;
    iter = sufmap.begin();
    while(iter != sufmap.end()){
        std::cout << iter->first << " " << iter->second << std::endl;
        if(iter->second > max){
            sec = max;
            max = iter->second;
        }
        iter++;
    }

    const int k=3;
    if(max < k*sec){
        return 0;
    }

    //当一个后缀出现最多时，它的子后缀出现同样次数
    //例如.example.com和.com
    //本段将找出最长的后缀，能够找出多个不互为后缀的出现次数满足要求的
    //
    //注意不能先去掉子后缀再进行计数
    std::vector<std::string> maxv;
    iter = sufmap.begin();
    bool issuf;
    while(iter != sufmap.end()){
        if(iter->second == max){
            issuf = false;
            for(int i=0;i<maxv.size();++i){
                if(is_suffix(maxv[i], iter->first)){
                    issuf = true;
                    break;
                }else if(is_suffix(iter->first, maxv[i])){
                    maxv.erase(maxv.begin()+i);
                    break;
                }
            }
            if(!issuf){
                maxv.push_back(iter->first);
            }
        }
        iter++;
    }

    simple_print("-----");
    for(int i=0;i<maxv.size();++i){
        char s[256];
        maxv[i].copy(s, maxv[i].size());
        domain2qname(s, maxv[i].size());
        simple_print(s);
    }

    return 0;
}

生成并部署过滤器

过滤器中将使用BPF_MAP_TYPE_LPM_TRIE，详见空间中XDP之BPF_MAP_TYPE_LPM_TRIE的使用

在上一步中得到了要过滤的域名后缀，为了使用LPM trie，将后缀倒序存入map中，XDP程序的内核部分也将提取出域名，逆序处理后查询map，判断是不是要阻拦。

内核部分

/* SPDX-License-Identifier: GPL-2.0 */
#include <linux/bpf.h>
#include <linux/in.h>

#include <linux/if_ether.h>
#include <bpf/bpf_helpers.h>
#include <bpf/bpf_endian.h>

// The parsing helper functions from the packet01 lesson have moved here
#include "../common/parsing_helpers.h"
#include "../common/rewrite_helpers.h"
#define bpf_printk(fmt, ...)				\
({                                                      \
        char ____fmt[] = fmt;                           \
        bpf_trace_printk(____fmt, sizeof(____fmt),      \
                         ##__VA_ARGS__);                \
})

#define DM_MAXLEN 64
#define SUF_MAXLEN 64

struct qname_lpm_key {
	__u32 prefixlen;
	char rev_suf[SUF_MAXLEN];
};

struct {
        __uint(type, BPF_MAP_TYPE_LPM_TRIE);
        __type(key, struct qname_lpm_key);
        __type(value, __u32);
        __uint(map_flags, BPF_F_NO_PREALLOC);
        __uint(max_entries, 255);
} dns_block_suffixes SEC(".maps");

static __always_inline struct qname_lpm_key get_qname_lpm_key(const char* base, void* data_end){
	struct qname_lpm_key qlk = {
		.prefixlen = SUF_MAXLEN,
		.rev_suf = {0}
	};
	__u64 qend = 0;
	char tmp = 0, sv = 0;
	char qnbuf[DM_MAXLEN] = {0};

	while(qend<DM_MAXLEN){
		if((void*)base+qend+1 > data_end) goto fail;
		if(qend == tmp){
			sv = tmp;
			tmp = base[qend];
			bpf_printk("dm len:%d\n", tmp);
			if(tmp == 0x00) break;
			if(tmp > 63) goto fail;
			qnbuf[qend] = '.';
			tmp = sv+tmp+1;
		}else{
			qnbuf[qend] = base[qend];
		}
		qend++;
	}
	if(qend >= DM_MAXLEN) goto fail;

	__u64 qlen = qend-1;
	qend--;
	while(qend > 0){
		__u64 i = qlen-qend;
		if(i>=SUF_MAXLEN) break;
		if(qend<0 || qend>DM_MAXLEN-1) goto fail;
		qlk.rev_suf[i] = qnbuf[qend];
		qend--;
	}

	bpf_printk("rev suffix:%s\n", qlk.rev_suf);
	return qlk;

fail:
	qlk.prefixlen = 0;
	return qlk;
}

/*
 * Solution to the assignment 1 in lesson packet02
 */
SEC("xdp_patch_ports")
int xdp_patch_ports_func(struct xdp_md *ctx)
{
	int action = XDP_PASS;
	int eth_type, ip_type;
	struct ethhdr *eth;
	struct iphdr *iphdr;
	struct ipv6hdr *ipv6hdr;
	struct udphdr *udphdr;
	void *data_end = (void *)(long)ctx->data_end;
	void *data = (void *)(long)ctx->data;
	struct hdr_cursor nh = { .pos = data };

	eth_type = parse_ethhdr(&nh, data_end, &eth);
	if (eth_type < 0) {
		action = XDP_ABORTED;
		goto out;
	}

	if (eth_type == bpf_htons(ETH_P_IP)) {
		ip_type = parse_iphdr(&nh, data_end, &iphdr);
	} else if (eth_type == bpf_htons(ETH_P_IPV6)) {
		ip_type = parse_ip6hdr(&nh, data_end, &ipv6hdr);
	} else {
		goto out;
	}

	if (ip_type == IPPROTO_UDP) {
		__u32 udppld = parse_udphdr(&nh, data_end, &udphdr);
		if (udppld < 0) {
			action = XDP_ABORTED;
			goto out;
		}
		if((__u8*)(nh.pos) + 12 > data_end){
			action = XDP_PASS;
			goto out;
		}
		__u16 qrn = *(((__u16*)(nh.pos))+2);
		if(qrn > 0){
			struct qname_lpm_key qlk = get_qname_lpm_key((char*)nh.pos+12, data_end);
			if(qlk.prefixlen == 0){
				action = XDP_ABORTED;
				goto out;
			}
			__u32* tval = NULL;
			if(!(tval = bpf_map_lookup_elem(&dns_block_suffixes, &qlk))){
				action = XDP_PASS;
				goto out;
			}else{
				bpf_printk("blocked prefix: %d", *tval);
			}
		}
	} else {
		goto out;
	}

out:
	return action;
}

char _license[] SEC("license") = "GPL";

用户部分

//修改自xdp-tutorial，有冗余，map的核心操作见170行左右

/* SPDX-License-Identifier: GPL-2.0 */
static const char *__doc__ = "Simple XDP prog doing XDP_PASS\n";

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <getopt.h>
#include <string.h>

#include <bpf/bpf.h>
#include <bpf/libbpf.h>

#include <net/if.h>
#include <linux/if_link.h> /* depend on kernel-headers installed */

#include "../common/common_params.h"

#define DM_MAXLEN 64
#define SUF_MAXLEN 64

struct qname_lpm_key {
	__u32 prefixlen;
	char rev_suf[SUF_MAXLEN];
};


static const struct option_wrapper long_options[] = {
	{{"help",        no_argument,		NULL, 'h' },
	 "Show help", false},

	{{"dev",         required_argument,	NULL, 'd' },
	 "Operate on device <ifname>", "<ifname>", true},

	{{"skb-mode",    no_argument,		NULL, 'S' },
	 "Install XDP program in SKB (AKA generic) mode"},

	{{"native-mode", no_argument,		NULL, 'N' },
	 "Install XDP program in native mode"},

	{{"auto-mode",   no_argument,		NULL, 'A' },
	 "Auto-detect SKB or native mode"},

	{{"force",       no_argument,		NULL, 'F' },
	 "Force install, replacing existing program on interface"},

	{{"unload",      no_argument,		NULL, 'U' },
	 "Unload XDP program instead of loading"},

	{{0, 0, NULL,  0 }, NULL, false}
};

int load_bpf_object_file__simple(const char *filename, struct bpf_object** o_obj)
{
	int first_prog_fd = -1;
	struct bpf_object *obj;
	int err;

	/* Use libbpf for extracting BPF byte-code from BPF-ELF object, and
	 * loading this into the kernel via bpf-syscall
	 */
	err = bpf_prog_load(filename, BPF_PROG_TYPE_XDP, &obj, &first_prog_fd);
	if (err) {
		fprintf(stderr, "ERR: loading BPF-OBJ file(%s) (%d): %s\n",
			filename, err, strerror(-err));
		*o_obj = NULL;
        return -1;
	}

	/* Simply return the first program file descriptor.
	 * (Hint: This will get more advanced later)
	 */
    *o_obj = obj;
	return first_prog_fd;
}

static int xdp_link_detach(int ifindex, __u32 xdp_flags)
{
	/* Next assignment this will move into ../common/
	 * (in more generic version)
	 */
	int err;

	if ((err = bpf_set_link_xdp_fd(ifindex, -1, xdp_flags)) < 0) {
		fprintf(stderr, "ERR: link set xdp unload failed (err=%d):%s\n",
			err, strerror(-err));
		return EXIT_FAIL_XDP;
	}
	return EXIT_OK;
}

int xdp_link_attach(int ifindex, __u32 xdp_flags, int prog_fd)
{
	/* Next assignment this will move into ../common/ */
	int err;

	/* libbpf provide the XDP net_device link-level hook attach helper */
	err = bpf_set_link_xdp_fd(ifindex, prog_fd, xdp_flags);
	if (err == -EEXIST && !(xdp_flags & XDP_FLAGS_UPDATE_IF_NOEXIST)) {
		/* Force mode didn't work, probably because a program of the
		 * opposite type is loaded. Let's unload that and try loading
		 * again.
		 */

		__u32 old_flags = xdp_flags;

		xdp_flags &= ~XDP_FLAGS_MODES;
		xdp_flags |= (old_flags & XDP_FLAGS_SKB_MODE) ? XDP_FLAGS_DRV_MODE : XDP_FLAGS_SKB_MODE;
		err = bpf_set_link_xdp_fd(ifindex, -1, xdp_flags);
		if (!err)
			err = bpf_set_link_xdp_fd(ifindex, prog_fd, old_flags);
	}

	if (err < 0) {
		fprintf(stderr, "ERR: "
			"ifindex(%d) link set xdp fd failed (%d): %s\n",
			ifindex, -err, strerror(-err));

		switch (-err) {
		case EBUSY:
		case EEXIST:
			fprintf(stderr, "Hint: XDP already loaded on device"
				" use --force to swap/replace\n");
			break;
		case EOPNOTSUPP:
			fprintf(stderr, "Hint: Native-XDP not supported"
				" use --skb-mode or --auto-mode\n");
			break;
		default:
			break;
		}
		return EXIT_FAIL_XDP;
	}

	return EXIT_OK;
}

int main(int argc, char **argv)
{
	struct bpf_prog_info info = {};
	__u32 info_len = sizeof(info);
	char filename[256] = "lpm_test.o";
	int prog_fd, err;

	struct config cfg = {
		.xdp_flags = XDP_FLAGS_UPDATE_IF_NOEXIST | XDP_FLAGS_DRV_MODE,
		.ifindex   = -1,
		.do_unload = false,
	};

	parse_cmdline_args(argc, argv, long_options, &cfg, __doc__);
	/* Required option */
	if (cfg.ifindex == -1) {
		fprintf(stderr, "ERR: required option --dev missing\n");
		usage(argv[0], __doc__, long_options, (argc == 1));
		return EXIT_FAIL_OPTION;
	}
	if (cfg.do_unload)
		return xdp_link_detach(cfg.ifindex, cfg.xdp_flags);

    struct bpf_object *obj;

	/* Load the BPF-ELF object file and get back first BPF_prog FD */
	prog_fd = load_bpf_object_file__simple(filename, &obj);
	if (prog_fd <= 0) {
		fprintf(stderr, "ERR: loading file: %s\n", filename);
		return EXIT_FAIL_BPF;
	}

    struct bpf_map *dmap = NULL;
    if(!(dmap = bpf_object__find_map_by_name(obj, "dns_block_suffixes"))){
        fprintf(stderr, "ERR: loading map: %s\n", "dns_block_suffixes");
		return EXIT_FAIL_BPF;
    }
	int dmap_fd = bpf_map__fd(dmap);
    
	int fp;
	char fname[256] = "../block_domains.t";
	if((fp = fopen(fname,"r")) == NULL){
	perror("fail to read");
	exit (1) ;
	}

	char buf[SUF_MAXLEN] = {0};
	__u32 len;
	int cnt = 0;
	struct qname_lpm_key qlk;
	while(fgets(buf,SUF_MAXLEN,fp) != NULL){
		len = strlen(buf);
		buf[len-1] = '\0';  /*去掉换行符*/
		
		strrev(buf);
		memset(qlk.rev_suf, 0, SUF_MAXLEN);
		qlk.prefixlen = len-1;
		strncpy(qlk.rev_suf, buf, len);
		bpf_map_update_elem(dmap_fd, &qlk, cnt, BPF_ANY);
		memset(buf, 0, SUF_MAXLEN);
		cnt++;
	}

	/* At this point: BPF-prog is (only) loaded by the kernel, and prog_fd
	 * is our file-descriptor handle. Next step is attaching this FD to a
	 * kernel hook point, in this case XDP net_device link-level hook.
	 * Fortunately libbpf have a helper for this:
	 */
	err = xdp_link_attach(cfg.ifindex, cfg.xdp_flags, prog_fd);
	if (err)
		return err;

        /* This step is not really needed , BPF-info via bpf-syscall */
	err = bpf_obj_get_info_by_fd(prog_fd, &info, &info_len);
	if (err) {
		fprintf(stderr, "ERR: can't get prog info - %s\n",
			strerror(errno));
		return err;
	}

	printf("Success: Loading "
	       "XDP prog name:%s(id:%d) on device:%s(ifindex:%d)\n",
	       info.name, info.id, cfg.ifname, cfg.ifindex);
	return EXIT_OK;
}