flydean

flydean 查看完整档案

深圳编辑清华大学  |  工业工程 编辑程序那些事  |  主创 编辑 www.flydean.com 编辑
编辑

欢迎访问我的个人网站:www.flydean.com
最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧,尽在公众号:程序那些事!

个人动态

flydean 收藏了文章 · 9月25日

java安全编码指南之:可见性和原子性

简介

java类中会定义很多变量,有类变量也有实例变量,这些变量在访问的过程中,会遇到一些可见性和原子性的问题。这里我们来详细了解一下怎么避免这些问题。

不可变对象的可见性

不可变对象就是初始化之后不能够被修改的对象,那么是不是类中引入了不可变对象,所有对不可变对象的修改都立马对所有线程可见呢?

实际上,不可变对象只能保证在多线程环境中,对象使用的安全性,并不能够保证对象的可见性。

先来讨论一下可变性,我们考虑下面的一个例子:

public final class ImmutableObject {
    private final int age;
    public ImmutableObject(int age){
        this.age=age;
    }
}

我们定义了一个ImmutableObject对象,class是final的,并且里面的唯一字段也是final的。所以这个ImmutableObject初始化之后就不能够改变。

然后我们定义一个类来get和set这个ImmutableObject:

public class ObjectWithNothing {
    private ImmutableObject refObject;
    public ImmutableObject getImmutableObject(){
        return refObject;
    }
    public void setImmutableObject(int age){
        this.refObject=new ImmutableObject(age);
    }
}

上面的例子中,我们定义了一个对不可变对象的引用refObject,然后定义了get和set方法。

注意,虽然ImmutableObject这个类本身是不可变的,但是我们对该对象的引用refObject是可变的。这就意味着我们可以调用多次setImmutableObject方法。

再来讨论一下可见性。

上面的例子中,在多线程环境中,是不是每次setImmutableObject都会导致getImmutableObject返回一个新的值呢?

答案是否定的。

当把源码编译之后,在编译器中生成的指令的顺序跟源码的顺序并不是完全一致的。处理器可能采用乱序或者并行的方式来执行指令(在JVM中只要程序的最终执行结果和在严格串行环境中执行结果一致,这种重排序是允许的)。并且处理器还有本地缓存,当将结果存储在本地缓存中,其他线程是无法看到结果的。除此之外缓存提交到主内存的顺序也肯能会变化。

怎么解决呢?

最简单的解决可见性的办法就是加上volatile关键字,volatile关键字可以使用java内存模型的happens-before规则,从而保证volatile的变量修改对所有线程可见。

public class ObjectWithVolatile {
    private volatile ImmutableObject refObject;
    public ImmutableObject getImmutableObject(){
        return refObject;
    }
    public void setImmutableObject(int age){
        this.refObject=new ImmutableObject(age);
    }
}

另外,使用锁机制,也可以达到同样的效果:

public class ObjectWithSync {
    private  ImmutableObject refObject;
    public synchronized ImmutableObject getImmutableObject(){
        return refObject;
    }
    public synchronized void setImmutableObject(int age){
        this.refObject=new ImmutableObject(age);
    }
}

最后,我们还可以使用原子类来达到同样的效果:

public class ObjectWithAtomic {
    private final AtomicReference<ImmutableObject> refObject= new AtomicReference<>();
    public ImmutableObject getImmutableObject(){
        return refObject.get();
    }
    public void setImmutableObject(int age){
        refObject.set(new ImmutableObject(age));
    }
}

保证共享变量的复合操作的原子性

如果是共享对象,那么我们就需要考虑在多线程环境中的原子性。如果是对共享变量的复合操作,比如:++, -- *=, /=, %=, +=, -=, <<=, >>=, >>>=, ^= 等,看起来是一个语句,但实际上是多个语句的集合。

我们需要考虑多线程下面的安全性。

考虑下面的例子:

public class CompoundOper1 {
    private int i=0;
    public int increase(){
        i++;
        return i;
    }
}

例子中我们对int i进行累加操作。但是++实际上是由三个操作组成的:

  1. 从内存中读取i的值,并写入CPU寄存器中。
  2. CPU寄存器中将i值+1
  3. 将值写回内存中的i中。

如果在单线程环境中,是没有问题的,但是在多线程环境中,因为不是原子操作,就可能会发生问题。

解决办法有很多种,第一种就是使用synchronized关键字

    public synchronized int increaseSync(){
        i++;
        return i;
    }

第二种就是使用lock:

    private final ReentrantLock reentrantLock=new ReentrantLock();

    public int increaseWithLock(){
        try{
            reentrantLock.lock();
            i++;
            return i;
        }finally {
            reentrantLock.unlock();
        }
    }

第三种就是使用Atomic原子类:

    private AtomicInteger atomicInteger=new AtomicInteger(0);

    public int increaseWithAtomic(){
        return atomicInteger.incrementAndGet();
    }

保证多个Atomic原子类操作的原子性

如果一个方法使用了多个原子类的操作,虽然单个原子操作是原子性的,但是组合起来就不一定了。

我们看一个例子:

public class CompoundAtomic {
    private AtomicInteger atomicInteger1=new AtomicInteger(0);
    private AtomicInteger atomicInteger2=new AtomicInteger(0);

    public void update(){
        atomicInteger1.set(20);
        atomicInteger2.set(10);
    }

    public int get() {
        return atomicInteger1.get()+atomicInteger2.get();
    }
}

上面的例子中,我们定义了两个AtomicInteger,并且分别在update和get操作中对两个AtomicInteger进行操作。

虽然AtomicInteger是原子性的,但是两个不同的AtomicInteger合并起来就不是了。在多线程操作的过程中可能会遇到问题。

同样的,我们可以使用同步机制或者锁来保证数据的一致性。

保证方法调用链的原子性

如果我们要创建一个对象的实例,而这个对象的实例是通过链式调用来创建的。那么我们需要保证链式调用的原子性。

考虑下面的一个例子:

public class ChainedMethod {
    private int age=0;
    private String name="";
    private String adress="";

    public ChainedMethod setAdress(String adress) {
        this.adress = adress;
        return this;
    }

    public ChainedMethod setAge(int age) {
        this.age = age;
        return this;
    }

    public ChainedMethod setName(String name) {
        this.name = name;
        return this;
    }
}

很简单的一个对象,我们定义了三个属性,每次set都会返回对this的引用。

我们看下在多线程环境下面怎么调用:

        ChainedMethod chainedMethod= new ChainedMethod();
        Thread t1 = new Thread(() -> chainedMethod.setAge(1).setAdress("www.flydean.com1").setName("name1"));
        t1.start();

        Thread t2 = new Thread(() -> chainedMethod.setAge(2).setAdress("www.flydean.com2").setName("name2"));
        t2.start();

因为在多线程环境下,上面的set方法可能会出现混乱的情况。

怎么解决呢?我们可以先创建一个本地的副本,这个副本因为是本地访问的,所以是线程安全的,最后将副本拷贝给新创建的实例对象。

主要的代码是下面样子的:

public class ChainedMethodWithBuilder {
    private int age=0;
    private String name="";
    private String adress="";

    public ChainedMethodWithBuilder(Builder builder){
        this.adress=builder.adress;
        this.age=builder.age;
        this.name=builder.name;
    }

    public static class Builder{
        private int age=0;
        private String name="";
        private String adress="";

        public static Builder newInstance(){
            return new Builder();
        }
        private Builder() {}

        public Builder setName(String name) {
            this.name = name;
            return this;
        }

        public Builder setAge(int age) {
            this.age = age;
            return this;
        }

        public Builder setAdress(String adress) {
            this.adress = adress;
            return this;
        }

        public ChainedMethodWithBuilder build(){
            return new ChainedMethodWithBuilder(this);
        }
    }

我们看下怎么调用:

      final ChainedMethodWithBuilder[] builder = new ChainedMethodWithBuilder[1];
        Thread t1 = new Thread(() -> {
            builder[0] =ChainedMethodWithBuilder.Builder.newInstance()
                .setAge(1).setAdress("www.flydean.com1").setName("name1")
                .build();});
        t1.start();

        Thread t2 = new Thread(() ->{
            builder[0] =ChainedMethodWithBuilder.Builder.newInstance()
                .setAge(1).setAdress("www.flydean.com1").setName("name1")
                .build();});
        t2.start();

因为lambda表达式中使用的变量必须是final或者final等效的,所以我们需要构建一个final的数组。

读写64bits的值

在java中,64bits的long和double是被当成两个32bits来对待的。

所以一个64bits的操作被分成了两个32bits的操作。从而导致了原子性问题。

考虑下面的代码:

public class LongUsage {
    private long i =0;

    public void setLong(long i){
        this.i=i;
    }
    public void printLong(){
        System.out.println("i="+i);
    }
}

因为long的读写是分成两部分进行的,如果在多线程的环境中多次调用setLong和printLong的方法,就有可能会出现问题。

解决办法本简单,将long或者double变量定义为volatile即可。

private volatile long i = 0;

本文的代码:

learn-java-base-9-to-20/tree/master/security

本文已收录于 http://www.flydean.com/java-security-code-line-visibility-atomicity/

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

查看原文

flydean 发布了文章 · 9月25日

java安全编码指南之:可见性和原子性

简介

java类中会定义很多变量,有类变量也有实例变量,这些变量在访问的过程中,会遇到一些可见性和原子性的问题。这里我们来详细了解一下怎么避免这些问题。

不可变对象的可见性

不可变对象就是初始化之后不能够被修改的对象,那么是不是类中引入了不可变对象,所有对不可变对象的修改都立马对所有线程可见呢?

实际上,不可变对象只能保证在多线程环境中,对象使用的安全性,并不能够保证对象的可见性。

先来讨论一下可变性,我们考虑下面的一个例子:

public final class ImmutableObject {
    private final int age;
    public ImmutableObject(int age){
        this.age=age;
    }
}

我们定义了一个ImmutableObject对象,class是final的,并且里面的唯一字段也是final的。所以这个ImmutableObject初始化之后就不能够改变。

然后我们定义一个类来get和set这个ImmutableObject:

public class ObjectWithNothing {
    private ImmutableObject refObject;
    public ImmutableObject getImmutableObject(){
        return refObject;
    }
    public void setImmutableObject(int age){
        this.refObject=new ImmutableObject(age);
    }
}

上面的例子中,我们定义了一个对不可变对象的引用refObject,然后定义了get和set方法。

注意,虽然ImmutableObject这个类本身是不可变的,但是我们对该对象的引用refObject是可变的。这就意味着我们可以调用多次setImmutableObject方法。

再来讨论一下可见性。

上面的例子中,在多线程环境中,是不是每次setImmutableObject都会导致getImmutableObject返回一个新的值呢?

答案是否定的。

当把源码编译之后,在编译器中生成的指令的顺序跟源码的顺序并不是完全一致的。处理器可能采用乱序或者并行的方式来执行指令(在JVM中只要程序的最终执行结果和在严格串行环境中执行结果一致,这种重排序是允许的)。并且处理器还有本地缓存,当将结果存储在本地缓存中,其他线程是无法看到结果的。除此之外缓存提交到主内存的顺序也肯能会变化。

怎么解决呢?

最简单的解决可见性的办法就是加上volatile关键字,volatile关键字可以使用java内存模型的happens-before规则,从而保证volatile的变量修改对所有线程可见。

public class ObjectWithVolatile {
    private volatile ImmutableObject refObject;
    public ImmutableObject getImmutableObject(){
        return refObject;
    }
    public void setImmutableObject(int age){
        this.refObject=new ImmutableObject(age);
    }
}

另外,使用锁机制,也可以达到同样的效果:

public class ObjectWithSync {
    private  ImmutableObject refObject;
    public synchronized ImmutableObject getImmutableObject(){
        return refObject;
    }
    public synchronized void setImmutableObject(int age){
        this.refObject=new ImmutableObject(age);
    }
}

最后,我们还可以使用原子类来达到同样的效果:

public class ObjectWithAtomic {
    private final AtomicReference<ImmutableObject> refObject= new AtomicReference<>();
    public ImmutableObject getImmutableObject(){
        return refObject.get();
    }
    public void setImmutableObject(int age){
        refObject.set(new ImmutableObject(age));
    }
}

保证共享变量的复合操作的原子性

如果是共享对象,那么我们就需要考虑在多线程环境中的原子性。如果是对共享变量的复合操作,比如:++, -- *=, /=, %=, +=, -=, <<=, >>=, >>>=, ^= 等,看起来是一个语句,但实际上是多个语句的集合。

我们需要考虑多线程下面的安全性。

考虑下面的例子:

public class CompoundOper1 {
    private int i=0;
    public int increase(){
        i++;
        return i;
    }
}

例子中我们对int i进行累加操作。但是++实际上是由三个操作组成的:

  1. 从内存中读取i的值,并写入CPU寄存器中。
  2. CPU寄存器中将i值+1
  3. 将值写回内存中的i中。

如果在单线程环境中,是没有问题的,但是在多线程环境中,因为不是原子操作,就可能会发生问题。

解决办法有很多种,第一种就是使用synchronized关键字

    public synchronized int increaseSync(){
        i++;
        return i;
    }

第二种就是使用lock:

    private final ReentrantLock reentrantLock=new ReentrantLock();

    public int increaseWithLock(){
        try{
            reentrantLock.lock();
            i++;
            return i;
        }finally {
            reentrantLock.unlock();
        }
    }

第三种就是使用Atomic原子类:

    private AtomicInteger atomicInteger=new AtomicInteger(0);

    public int increaseWithAtomic(){
        return atomicInteger.incrementAndGet();
    }

保证多个Atomic原子类操作的原子性

如果一个方法使用了多个原子类的操作,虽然单个原子操作是原子性的,但是组合起来就不一定了。

我们看一个例子:

public class CompoundAtomic {
    private AtomicInteger atomicInteger1=new AtomicInteger(0);
    private AtomicInteger atomicInteger2=new AtomicInteger(0);

    public void update(){
        atomicInteger1.set(20);
        atomicInteger2.set(10);
    }

    public int get() {
        return atomicInteger1.get()+atomicInteger2.get();
    }
}

上面的例子中,我们定义了两个AtomicInteger,并且分别在update和get操作中对两个AtomicInteger进行操作。

虽然AtomicInteger是原子性的,但是两个不同的AtomicInteger合并起来就不是了。在多线程操作的过程中可能会遇到问题。

同样的,我们可以使用同步机制或者锁来保证数据的一致性。

保证方法调用链的原子性

如果我们要创建一个对象的实例,而这个对象的实例是通过链式调用来创建的。那么我们需要保证链式调用的原子性。

考虑下面的一个例子:

public class ChainedMethod {
    private int age=0;
    private String name="";
    private String adress="";

    public ChainedMethod setAdress(String adress) {
        this.adress = adress;
        return this;
    }

    public ChainedMethod setAge(int age) {
        this.age = age;
        return this;
    }

    public ChainedMethod setName(String name) {
        this.name = name;
        return this;
    }
}

很简单的一个对象,我们定义了三个属性,每次set都会返回对this的引用。

我们看下在多线程环境下面怎么调用:

        ChainedMethod chainedMethod= new ChainedMethod();
        Thread t1 = new Thread(() -> chainedMethod.setAge(1).setAdress("www.flydean.com1").setName("name1"));
        t1.start();

        Thread t2 = new Thread(() -> chainedMethod.setAge(2).setAdress("www.flydean.com2").setName("name2"));
        t2.start();

因为在多线程环境下,上面的set方法可能会出现混乱的情况。

怎么解决呢?我们可以先创建一个本地的副本,这个副本因为是本地访问的,所以是线程安全的,最后将副本拷贝给新创建的实例对象。

主要的代码是下面样子的:

public class ChainedMethodWithBuilder {
    private int age=0;
    private String name="";
    private String adress="";

    public ChainedMethodWithBuilder(Builder builder){
        this.adress=builder.adress;
        this.age=builder.age;
        this.name=builder.name;
    }

    public static class Builder{
        private int age=0;
        private String name="";
        private String adress="";

        public static Builder newInstance(){
            return new Builder();
        }
        private Builder() {}

        public Builder setName(String name) {
            this.name = name;
            return this;
        }

        public Builder setAge(int age) {
            this.age = age;
            return this;
        }

        public Builder setAdress(String adress) {
            this.adress = adress;
            return this;
        }

        public ChainedMethodWithBuilder build(){
            return new ChainedMethodWithBuilder(this);
        }
    }

我们看下怎么调用:

      final ChainedMethodWithBuilder[] builder = new ChainedMethodWithBuilder[1];
        Thread t1 = new Thread(() -> {
            builder[0] =ChainedMethodWithBuilder.Builder.newInstance()
                .setAge(1).setAdress("www.flydean.com1").setName("name1")
                .build();});
        t1.start();

        Thread t2 = new Thread(() ->{
            builder[0] =ChainedMethodWithBuilder.Builder.newInstance()
                .setAge(1).setAdress("www.flydean.com1").setName("name1")
                .build();});
        t2.start();

因为lambda表达式中使用的变量必须是final或者final等效的,所以我们需要构建一个final的数组。

读写64bits的值

在java中,64bits的long和double是被当成两个32bits来对待的。

所以一个64bits的操作被分成了两个32bits的操作。从而导致了原子性问题。

考虑下面的代码:

public class LongUsage {
    private long i =0;

    public void setLong(long i){
        this.i=i;
    }
    public void printLong(){
        System.out.println("i="+i);
    }
}

因为long的读写是分成两部分进行的,如果在多线程的环境中多次调用setLong和printLong的方法,就有可能会出现问题。

解决办法本简单,将long或者double变量定义为volatile即可。

private volatile long i = 0;

本文的代码:

learn-java-base-9-to-20/tree/master/security

本文已收录于 http://www.flydean.com/java-security-code-line-visibility-atomicity/

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

查看原文

赞 1 收藏 1 评论 0

flydean 收藏了文章 · 9月23日

看动画学算法之:排序-count排序

简介

今天我们介绍一种不需要作比较就能排序的算法:count排序。

count排序是一种空间换时间的算法,我们借助一个外部的count数组来统计各个元素出现的次数,从而最终完成排序。

count排序的例子

count排序有一定的限制,因为外部的count数组长度是和原数组的元素范围是一致的,所以count排序一般只适合数组中元素范围比较小的情况。

我们举一个0-9的元素的排序的例子:3,4,2,5,6,2,4,9,1,3,5。

先看一个动画,看看是怎么排序的:

count数组里面存放的是从0到9这些元素出现的次数。

我们遍历原始数组,遇到相应的数字就给相应的count+1。

等所有的元素都count之后,再根据count数组中的值还原排序过后的数组。

count排序的java实现

count排序很简单,我们主要掌握下面两个大的步骤:

  1. 遍历原始数组,构建count数组。
  2. 根据count数组中的count值,重新构建排序数组。
public class CountingSort {

    public void doCountingSort(int[] array){
        int n = array.length;

        // 存储排序过后的数组
        int output[] = new int[n];

        // count数组,用来存储统计各个元素出现的次数
        int count[] = new int[10];
        for (int i=0; i<10; ++i) {
            count[i] = 0;
        }
        log.info("初始化count值:{}",count);

        // 将原始数组中数据出现次数存入count数组
        for (int i=0; i<n; ++i) {
            ++count[array[i]];
        }
        log.info("count之后count值:{}",count);

        //遍历count,将相应的数据插入output
        int j=0;
        for(int i=0; i<10; i++){
            while(count[i]-- > 0){
                output[j++]=i;
            }
        }
        log.info("构建output之后的output值:{}",output);

        //将排序后的数组写回原数组
        for (int i = 0; i<n; ++i)
            array[i] = output[i];
    }

    public static void main(String[] args) {
        int[] array= {3,4,2,5,6,2,4,9,1,3,5};
        CountingSort countingSort=new CountingSort();
        log.info("countingSort之前的数组为:{}",array);
        countingSort.doCountingSort(array);
    }
}

上面的注释应该很清楚了。

运行的结果如下:

count排序的第二种方法

在我们获得count数组中每个元素的个数之后,其实我们还有另外一个生成结果数组的办法:

// 这里是一个小技巧,我们根据count中元素出现的次数计算对应元素第一次应该出现在output中的下标。
        //这里的下标是从右往左数的
        for (int i=1; i<10; i++) {
            count[i] += count[i - 1];
        }
        log.info("整理count对应的output下标:{}",count);
        // 根据count中的下标,构建排序后的数组
        //插入一个之后,相应的count下标要减一
        for (int i = n-1; i>=0; i--)
        {
            output[count[array[i]]-1] = array[i];
            --count[array[i]];
        }
        log.info("构建output之后的output值:{}",output);

主要分为两步:

第一步我们根据count中元素出现的次数计算对应元素第一次应该出现在output中的下标。这里的下标是从右往左数的。

第二步根据count中的下标,构建排序后的数组,插入一个之后,相应的count下标要减一。

可能不是很好理解,大家可以结合输出结果反复琢磨一下。

count排序的时间复杂度

从上面的代码我们可以看到,count排序实际上只做了少量次数的遍历。所以它的时间复杂度是O(n)。

本文的代码地址:

learn-algorithm

本文已收录于 http://www.flydean.com/algorithm-count-sort/

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

查看原文

flydean 发布了文章 · 9月23日

看动画学算法之:排序-count排序

简介

今天我们介绍一种不需要作比较就能排序的算法:count排序。

count排序是一种空间换时间的算法,我们借助一个外部的count数组来统计各个元素出现的次数,从而最终完成排序。

count排序的例子

count排序有一定的限制,因为外部的count数组长度是和原数组的元素范围是一致的,所以count排序一般只适合数组中元素范围比较小的情况。

我们举一个0-9的元素的排序的例子:3,4,2,5,6,2,4,9,1,3,5。

先看一个动画,看看是怎么排序的:

count数组里面存放的是从0到9这些元素出现的次数。

我们遍历原始数组,遇到相应的数字就给相应的count+1。

等所有的元素都count之后,再根据count数组中的值还原排序过后的数组。

count排序的java实现

count排序很简单,我们主要掌握下面两个大的步骤:

  1. 遍历原始数组,构建count数组。
  2. 根据count数组中的count值,重新构建排序数组。
public class CountingSort {

    public void doCountingSort(int[] array){
        int n = array.length;

        // 存储排序过后的数组
        int output[] = new int[n];

        // count数组,用来存储统计各个元素出现的次数
        int count[] = new int[10];
        for (int i=0; i<10; ++i) {
            count[i] = 0;
        }
        log.info("初始化count值:{}",count);

        // 将原始数组中数据出现次数存入count数组
        for (int i=0; i<n; ++i) {
            ++count[array[i]];
        }
        log.info("count之后count值:{}",count);

        //遍历count,将相应的数据插入output
        int j=0;
        for(int i=0; i<10; i++){
            while(count[i]-- > 0){
                output[j++]=i;
            }
        }
        log.info("构建output之后的output值:{}",output);

        //将排序后的数组写回原数组
        for (int i = 0; i<n; ++i)
            array[i] = output[i];
    }

    public static void main(String[] args) {
        int[] array= {3,4,2,5,6,2,4,9,1,3,5};
        CountingSort countingSort=new CountingSort();
        log.info("countingSort之前的数组为:{}",array);
        countingSort.doCountingSort(array);
    }
}

上面的注释应该很清楚了。

运行的结果如下:

count排序的第二种方法

在我们获得count数组中每个元素的个数之后,其实我们还有另外一个生成结果数组的办法:

// 这里是一个小技巧,我们根据count中元素出现的次数计算对应元素第一次应该出现在output中的下标。
        //这里的下标是从右往左数的
        for (int i=1; i<10; i++) {
            count[i] += count[i - 1];
        }
        log.info("整理count对应的output下标:{}",count);
        // 根据count中的下标,构建排序后的数组
        //插入一个之后,相应的count下标要减一
        for (int i = n-1; i>=0; i--)
        {
            output[count[array[i]]-1] = array[i];
            --count[array[i]];
        }
        log.info("构建output之后的output值:{}",output);

主要分为两步:

第一步我们根据count中元素出现的次数计算对应元素第一次应该出现在output中的下标。这里的下标是从右往左数的。

第二步根据count中的下标,构建排序后的数组,插入一个之后,相应的count下标要减一。

可能不是很好理解,大家可以结合输出结果反复琢磨一下。

count排序的时间复杂度

从上面的代码我们可以看到,count排序实际上只做了少量次数的遍历。所以它的时间复杂度是O(n)。

本文的代码地址:

learn-algorithm

本文已收录于 http://www.flydean.com/algorithm-count-sort/

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

查看原文

赞 1 收藏 1 评论 0

flydean 收藏了文章 · 9月22日

ECMAScript 6新特性简介

简介

ECMAScript 6.0(以下简称 ES6)是 JavaScript 语言的下一代标准,正式发布与2015年6月。它的目标,是使得JavaScript语言可以用来编写复杂的大型应用程序,成为企业级开发语言。

今天我们将会讲解一下ES6中引入的语法新特性。

ECMAScript和JavaScript的关系

1996年11月,JavaScript 的创造者 Netscape 公司,决定将 JavaScript 提交给国际标准化组织ECMA.

1997年, ECMA 发布262号标准文件 ECMAScript 1.0。

ECMAScript 和 JavaScript 的关系是,前者是后者的规格,后者是前者的一种实现。

我们看一下ECMAScript的发行历史:

从2015年ES2015,也就是ES6发布以来,ECMAScript以每年一个版本的发行速度发行到了ES2020。

后面的文章我们会讲解一下这些新版本的ECMAScript的新特性。

let和const

ES6中引入了let和const,是为了解决之前的var变量的种种问题。

在ES6之前,JS中变量的作用域有两种:全局作用域和函数作用域。

全局作用域很好理解,我们在浏览器控制台或者 Node.js 交互终端中开始编写 JavaScript 时,即进入了所谓的全局作用域。

全局作用域的变量可以在任何其他作用域中访问。

函数作用域就是定义在函数内部的变量,在函数内部都可以访问到该变量。

这两种作用域会有一些问题:

  1. 变量提升

var命令会发生”变量提升”现象,即变量可以在声明之前使用,值为undefined.

// var 的情况 
console.log(foo);  // 输出undefined 
var foo = 2; 
  1. 变量覆盖

当我们在函数作用域使用全局变量的时候,如果函数作用域中定义了同样名字的变量,不管是在哪里定义的,都会覆盖掉全局的变量。如下所示:

var tmp = new Date(); 
function f() { 
console.log(tmp); 
if (false) { var tmp = "hello world"; 
} } 
f(); // undefined
  1. 变量泄露

变量泄露的意思是,我们本来只希望在小范围作用域使用的变量,结果泄露到了范围外面,如下所示:

var s = 'hello'; 
for (var i = 0; i < s.length; i++) { 
console.log(s[i]); 
} 
console.log(i); // 5
~~

为了解决上面两个问题,ES6引入了let和const。

这两个都是块级作用域。不同的是const定义的变量初始化之后就不能变化了。

什么是块级作用域呢?类似于 if、switch 条件选择或者 for、while 这样的循环体即是所谓的块级作用域,或者更简单一点使用大括号括起来的就叫做块级作用域。

块级作用域的最大好处就是不会产生作用域提升,如下所示:

{
let a = 10;
var b = 1;
}
a // ReferenceError: a is not defined.
b // 1


# 解构赋值

什么是解构赋值呢?

ES6 允许按照一定模式,从数组和对象中提取值,对变量进行赋值,这被称为解构。

如下所示:

let [a, b, c] = [1, 2, 3];
let [ , , third] = ["foo", "bar", "baz"];
let [x, , y] = [1, 2, 3];
let [head, ...tail] = [1, 2, 3, 4];

let [x, y] = [1, 2, 3];


解构赋值还可以设定默认值,我们来看下面的几个例子:

let [foo = true] = [];
foo // true

let [x, y = 'b'] = ['a'];
// x='a', y='b'

let [x, y = 'b'] = ['a', undefined];
// x='a', y='b’

let [x = 1] = [undefined];
x // 1
let [x = 1] = [null];
x // null


如果解构的默认值是一个函数,那么可以触发惰性赋值:

function f() {
console.log('aaa');
}

let [x = f()] = [1];


上面的例子中,f函数将不会被执行。

除了结构变量之外,还可以结构对象:

let { bar, foo } = { foo: "aaa", bar: "bbb" };
foo // "aaa"
bar // "bbb"

let { baz } = { foo: "aaa", bar: "bbb" };
baz // undefined

var { foo: baz } = { foo: 'aaa', bar: 'bbb' };
baz // "aaa"

let obj = { first: 'hello', last: 'world' };
let { first: f, last: l } = obj;
f // 'hello'
l // 'world'


解构还支持嵌套的结构:

let obj = { p: [ 'Hello', { y: 'World' } ] };

let { p: [x, { y }] } = obj;

x // "Hello"
y // "World"


解构赋值有两个非常重要的作用。

第一就是交换变量:

let x = 1;
let y = 2;
[x, y] = [y, x];


我们就可以不再使用中间变量,直接进行两个变量值的交互。

第二个作用就是从函数中返回多个值:

// 返回一个数组
function example() { return [1, 2, 3]; }
let [a, b, c] = example();

// 返回一个对象
function example() { return { foo: 1, bar: 2 }; }
let { foo, bar } = example();

//提取JSON数据
let jsonData = { id: 42, status: "OK", data: [867, 5309] };
let { id, status, data: number } = jsonData;


# 数组的扩展

ES6中的Array.from方法用于将下面两类对象转为真正的数组:

* 类似数组的对象(array-like object)
* 可遍历(iterable)的对象(包括ES6新增的数据结构Set和Map)。

什么是类似数组对象呢?

所谓类似数组的对象,本质特征只有一点,即必须有length属性。因此,任何有length属性的对象,都可以通过Array.from方法转为数组。

下面的变量就是类数组变量:

let arrayLike = { '0': 'a', '1': 'b', '2': 'c', length: 3 };


这个类数组对象怎么转换成为数组呢?

// ES5的写法
var arr1 = [].slice.call(arrayLike);
// ['a', 'b', 'c']

// ES6的写法 let arr2 = Array.from(arrayLike);
// ['a', 'b', 'c']


我们看下通常的使用场景:

// NodeList对象
let ps = document.querySelectorAll('p');
Array.from(ps).forEach(function (p) { console.log(p); });

// arguments对象
function foo() { var args = Array.from(arguments);
// ...
}


什么是可遍历对象呢?

只要是部署了Iterator接口的数据结构,都叫做可遍历对象。

我们看下下面的例子:

Array.from('hello') // ['h', 'e', 'l', 'l', 'o']
let namesSet = new Set(['a', 'b'])
Array.from(namesSet) // ['a', 'b']


同时还引入了扩展运算符(...),通过扩展运算符,也可以很方便的转换为数组对象:

function foo() { var args = [...arguments]; } // arguments对象
[...document.querySelectorAll('div')] // NodeList对象


Array.from方法还可以接收第二个参数,用来对数组中的元素进行操作:

Array.from(arrayLike, x => x * x);
// 等同于
Array.from(arrayLike).map(x => x * x);

Array.from([1, 2, 3], (x) => x * x)
// [1, 4, 9]


Array.of方法可以很方便的创建新的数组:

Array.of(3, 11, 8) // [3,11,8]
Array.of(3) // [3]
Array.of(3).length // 1

Array() // []
Array(3) // [, , ,]
Array(3, 11, 8) // [3, 11, 8]


# 函数的扩展

ES6,可以支持函数的默认值了:

function log(x, y = 'World') { console.log(x, y); }
function Point(x = 0, y = 0) { this.x = x; this.y = y; }


函数的默认值可以和解构赋值默认值组合起来使用:

function foo({x, y = 5}) { console.log(x, y); }
foo({}) // undefined, 5
foo({x: 1}) // 1, 5
foo({x: 1, y: 2}) // 1, 2
foo() // TypeError: Cannot read property 'x' of undefined


接下来,我们看一个复杂的例子:

// 写法一
function m1({x = 0, y = 0} = {})
{ return [x, y]; }

// 写法二
function m2({x, y} = { x: 0, y: 0 })
{ return [x, y]; }


我们来看一下,上面的两种写法有什么不同呢?

当函数没有参数的情况:

m1() // [0, 0]
m2() // [0, 0]


当x和y都有值的情况:

m1({x: 3, y: 8}) // [3, 8]
m2({x: 3, y: 8}) // [3, 8]


当x有值,y无值的情况 :

m1({x: 3}) // [3, 0]
m2({x: 3}) // [3, undefined]


当x和y都无值的情况:

m1({}) // [0, 0];
m2({}) // [undefined, undefined]
m1({z: 3}) // [0, 0]
m2({z: 3}) // [undefined, undefined]


看出区别了吗? m1的解构赋值,对于x,y来说是有默认值0的。而m2的解构赋值对于x,y来说是没有默认值的。

> 本文作者:flydean程序那些事
> 
> 本文链接:[http://www.flydean.com/ecmascript-6-startup/](http://www.flydean.com/ecmascript-6-startup/)
> 
> 本文来源:flydean的博客
> 
> 欢迎关注我的公众号:「程序那些事」最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!














查看原文

flydean 发布了文章 · 9月22日

ECMAScript 6新特性简介

简介

ECMAScript 6.0(以下简称 ES6)是 JavaScript 语言的下一代标准,正式发布与2015年6月。它的目标,是使得JavaScript语言可以用来编写复杂的大型应用程序,成为企业级开发语言。

今天我们将会讲解一下ES6中引入的语法新特性。

ECMAScript和JavaScript的关系

1996年11月,JavaScript 的创造者 Netscape 公司,决定将 JavaScript 提交给国际标准化组织ECMA.

1997年, ECMA 发布262号标准文件 ECMAScript 1.0。

ECMAScript 和 JavaScript 的关系是,前者是后者的规格,后者是前者的一种实现。

我们看一下ECMAScript的发行历史:

从2015年ES2015,也就是ES6发布以来,ECMAScript以每年一个版本的发行速度发行到了ES2020。

后面的文章我们会讲解一下这些新版本的ECMAScript的新特性。

let和const

ES6中引入了let和const,是为了解决之前的var变量的种种问题。

在ES6之前,JS中变量的作用域有两种:全局作用域和函数作用域。

全局作用域很好理解,我们在浏览器控制台或者 Node.js 交互终端中开始编写 JavaScript 时,即进入了所谓的全局作用域。

全局作用域的变量可以在任何其他作用域中访问。

函数作用域就是定义在函数内部的变量,在函数内部都可以访问到该变量。

这两种作用域会有一些问题:

  1. 变量提升

var命令会发生”变量提升”现象,即变量可以在声明之前使用,值为undefined.

// var 的情况 
console.log(foo);  // 输出undefined 
var foo = 2; 
  1. 变量覆盖

当我们在函数作用域使用全局变量的时候,如果函数作用域中定义了同样名字的变量,不管是在哪里定义的,都会覆盖掉全局的变量。如下所示:

var tmp = new Date(); 
function f() { 
console.log(tmp); 
if (false) { var tmp = "hello world"; 
} } 
f(); // undefined
  1. 变量泄露

变量泄露的意思是,我们本来只希望在小范围作用域使用的变量,结果泄露到了范围外面,如下所示:

var s = 'hello'; 
for (var i = 0; i < s.length; i++) { 
console.log(s[i]); 
} 
console.log(i); // 5
~~

为了解决上面两个问题,ES6引入了let和const。

这两个都是块级作用域。不同的是const定义的变量初始化之后就不能变化了。

什么是块级作用域呢?类似于 if、switch 条件选择或者 for、while 这样的循环体即是所谓的块级作用域,或者更简单一点使用大括号括起来的就叫做块级作用域。

块级作用域的最大好处就是不会产生作用域提升,如下所示:

{
let a = 10;
var b = 1;
}
a // ReferenceError: a is not defined.
b // 1


# 解构赋值

什么是解构赋值呢?

ES6 允许按照一定模式,从数组和对象中提取值,对变量进行赋值,这被称为解构。

如下所示:

let [a, b, c] = [1, 2, 3];
let [ , , third] = ["foo", "bar", "baz"];
let [x, , y] = [1, 2, 3];
let [head, ...tail] = [1, 2, 3, 4];

let [x, y] = [1, 2, 3];


解构赋值还可以设定默认值,我们来看下面的几个例子:

let [foo = true] = [];
foo // true

let [x, y = 'b'] = ['a'];
// x='a', y='b'

let [x, y = 'b'] = ['a', undefined];
// x='a', y='b’

let [x = 1] = [undefined];
x // 1
let [x = 1] = [null];
x // null


如果解构的默认值是一个函数,那么可以触发惰性赋值:

function f() {
console.log('aaa');
}

let [x = f()] = [1];


上面的例子中,f函数将不会被执行。

除了结构变量之外,还可以结构对象:

let { bar, foo } = { foo: "aaa", bar: "bbb" };
foo // "aaa"
bar // "bbb"

let { baz } = { foo: "aaa", bar: "bbb" };
baz // undefined

var { foo: baz } = { foo: 'aaa', bar: 'bbb' };
baz // "aaa"

let obj = { first: 'hello', last: 'world' };
let { first: f, last: l } = obj;
f // 'hello'
l // 'world'


解构还支持嵌套的结构:

let obj = { p: [ 'Hello', { y: 'World' } ] };

let { p: [x, { y }] } = obj;

x // "Hello"
y // "World"


解构赋值有两个非常重要的作用。

第一就是交换变量:

let x = 1;
let y = 2;
[x, y] = [y, x];


我们就可以不再使用中间变量,直接进行两个变量值的交互。

第二个作用就是从函数中返回多个值:

// 返回一个数组
function example() { return [1, 2, 3]; }
let [a, b, c] = example();

// 返回一个对象
function example() { return { foo: 1, bar: 2 }; }
let { foo, bar } = example();

//提取JSON数据
let jsonData = { id: 42, status: "OK", data: [867, 5309] };
let { id, status, data: number } = jsonData;


# 数组的扩展

ES6中的Array.from方法用于将下面两类对象转为真正的数组:

* 类似数组的对象(array-like object)
* 可遍历(iterable)的对象(包括ES6新增的数据结构Set和Map)。

什么是类似数组对象呢?

所谓类似数组的对象,本质特征只有一点,即必须有length属性。因此,任何有length属性的对象,都可以通过Array.from方法转为数组。

下面的变量就是类数组变量:

let arrayLike = { '0': 'a', '1': 'b', '2': 'c', length: 3 };


这个类数组对象怎么转换成为数组呢?

// ES5的写法
var arr1 = [].slice.call(arrayLike);
// ['a', 'b', 'c']

// ES6的写法 let arr2 = Array.from(arrayLike);
// ['a', 'b', 'c']


我们看下通常的使用场景:

// NodeList对象
let ps = document.querySelectorAll('p');
Array.from(ps).forEach(function (p) { console.log(p); });

// arguments对象
function foo() { var args = Array.from(arguments);
// ...
}


什么是可遍历对象呢?

只要是部署了Iterator接口的数据结构,都叫做可遍历对象。

我们看下下面的例子:

Array.from('hello') // ['h', 'e', 'l', 'l', 'o']
let namesSet = new Set(['a', 'b'])
Array.from(namesSet) // ['a', 'b']


同时还引入了扩展运算符(...),通过扩展运算符,也可以很方便的转换为数组对象:

function foo() { var args = [...arguments]; } // arguments对象
[...document.querySelectorAll('div')] // NodeList对象


Array.from方法还可以接收第二个参数,用来对数组中的元素进行操作:

Array.from(arrayLike, x => x * x);
// 等同于
Array.from(arrayLike).map(x => x * x);

Array.from([1, 2, 3], (x) => x * x)
// [1, 4, 9]


Array.of方法可以很方便的创建新的数组:

Array.of(3, 11, 8) // [3,11,8]
Array.of(3) // [3]
Array.of(3).length // 1

Array() // []
Array(3) // [, , ,]
Array(3, 11, 8) // [3, 11, 8]


# 函数的扩展

ES6,可以支持函数的默认值了:

function log(x, y = 'World') { console.log(x, y); }
function Point(x = 0, y = 0) { this.x = x; this.y = y; }


函数的默认值可以和解构赋值默认值组合起来使用:

function foo({x, y = 5}) { console.log(x, y); }
foo({}) // undefined, 5
foo({x: 1}) // 1, 5
foo({x: 1, y: 2}) // 1, 2
foo() // TypeError: Cannot read property 'x' of undefined


接下来,我们看一个复杂的例子:

// 写法一
function m1({x = 0, y = 0} = {})
{ return [x, y]; }

// 写法二
function m2({x, y} = { x: 0, y: 0 })
{ return [x, y]; }


我们来看一下,上面的两种写法有什么不同呢?

当函数没有参数的情况:

m1() // [0, 0]
m2() // [0, 0]


当x和y都有值的情况:

m1({x: 3, y: 8}) // [3, 8]
m2({x: 3, y: 8}) // [3, 8]


当x有值,y无值的情况 :

m1({x: 3}) // [3, 0]
m2({x: 3}) // [3, undefined]


当x和y都无值的情况:

m1({}) // [0, 0];
m2({}) // [undefined, undefined]
m1({z: 3}) // [0, 0]
m2({z: 3}) // [undefined, undefined]


看出区别了吗? m1的解构赋值,对于x,y来说是有默认值0的。而m2的解构赋值对于x,y来说是没有默认值的。

> 本文作者:flydean程序那些事
> 
> 本文链接:[http://www.flydean.com/ecmascript-6-startup/](http://www.flydean.com/ecmascript-6-startup/)
> 
> 本文来源:flydean的博客
> 
> 欢迎关注我的公众号:「程序那些事」最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!














查看原文

赞 1 收藏 1 评论 1

flydean 收藏了文章 · 9月21日

java安全编码指南之:输入校验

简介

为了保证java程序的安全,任何外部用户的输入我们都认为是可能有恶意攻击意图,我们需要对所有的用户输入都进行一定程度的校验。

本文将带领大家探讨一下用户输入校验的一些场景。一起来看看吧。

在字符串标准化之后进行校验

通常我们在进行字符串校验的时候需要对一些特殊字符进行过滤,过滤之后再进行字符串的校验。

我们知道在java中字符是基于Unicode进行编码的。但是在Unicode中,同一个字符可能有不同的表示形式。所以我们需要对字符进行标准化。

java中有一个专门的类Normalizer来负责处理,字符标准化的问题。

我们看下面一个例子:

    public void testNormalizer(){
        System.out.println(Normalizer.normalize("\u00C1", Normalizer.Form.NFKC));
        System.out.println(Normalizer.normalize("\u0041\u0301", Normalizer.Form.NFKC));
    }

输出结果:

Á
Á

我们可以看到,虽然两者的Unicode不一样,但是最终表示的字符是一样的。所以我们在进行字符验证的时候,一定要先进行normalize处理。

考虑下面的例子:

    public void falseNormalize(){
        String s = "\uFE64" + "script" + "\uFE65";
        Pattern pattern = Pattern.compile("[<>]"); // 检查是否有尖括号
        Matcher matcher = pattern.matcher(s);
        if (matcher.find()) {
            throw new IllegalStateException();
        }
        s = Normalizer.normalize(s, Normalizer.Form.NFKC);
    }

其中uFE64表示的是<,而uFE65表示的是>,程序的本意是判断输入的字符串是否包含了尖括号,但是因为直接传入的是unicode字符,所以直接compile是检测不到的。

我们需要对代码进行下面的改动:

    public void trueNormalize(){
        String s = "\uFE64" + "script" + "\uFE65";
        s = Normalizer.normalize(s, Normalizer.Form.NFKC);
        Pattern pattern = Pattern.compile("[<>]"); // 检查是否有尖括号
        Matcher matcher = pattern.matcher(s);
        if (matcher.find()) {
            throw new IllegalStateException();
        }
    }

先进行normalize操作,然后再进行字符验证。

注意不可信字符串的格式化

我们经常会使用到格式化来对字符串进行格式化,在格式化的时候如果格式化字符串里面带有用户输入信息,那么我们就要注意了。

看下面的例子:

    public void wrongFormat(){
        Calendar c = new GregorianCalendar(2020, GregorianCalendar.JULY, 27);
        String input=" %1$tm";
        System.out.format(input + " 时间不匹配,应该是某个月的第 %1$terd 天", c);
    }

粗看一下没什么问题,但是我们的input中包含了格式化信息,最后输出结果:

 07 时间不匹配,应该是某个月的第 27rd 天

变相的,我们获取到了系统内部的信息,在某些情况下面,可能会暴露系统的内部逻辑。

上面的例子我们应该将input也作为一个参数,如下所示:

    public void rightFormat(){
        Calendar c = new GregorianCalendar(2020, GregorianCalendar.JULY, 27);
        String input=" %1$tm";
        System.out.format("%s 时间不匹配,应该是某个月的第 %terd 天",input, c);
    }

输出结果:

 %1$tm 时间不匹配,应该是某个月的第 27rd 天

小心使用Runtime.exec()

我们知道Runtime.exec()使用来调用系统命令的,如果有恶意的用户调用了“rm -rf /”,一切的一切都完蛋了。

所以,我们在调用Runtime.exec()的时候,一定要小心注意检测用户的输入。

看下面的一个例子:

    public void wrongExec() throws IOException {
        String dir = System.getProperty("dir");
        Runtime rt = Runtime.getRuntime();
        Process proc = rt.exec(new String[] {"sh", "-c", "ls " + dir});
    }

上面的例子中,我们从系统属性中读取dir,然后执行了系统的ls命令来查看dir中的内容。

如果有恶意用户给dir赋值成:

/usr & rm -rf /

那么系统实际上执行的命令就是:

sh -c 'ls /usr & rm -rf /'

从而导致恶意的删除。

解决上面的问题也有几个方法,第一个方法就是对输入做个校验,比如我们只运行dir包含特定的字符:

    public void correctExec1() throws IOException {
        String dir = System.getProperty("dir");
        if (!Pattern.matches("[0-9A-Za-z@.]+", dir)) {
            // Handle error
        }
        Runtime rt = Runtime.getRuntime();
        Process proc = rt.exec(new String[] {"sh", "-c", "ls " + dir});
    }

第二种方法就是使用switch语句,限定特定的输入:

    public void correctExec2(){
        String dir = System.getProperty("dir");
        switch (dir){
            case "/usr":
                System.out.println("/usr");
                break;
            case "/local":
                System.out.println("/local");
                break;
            default:
                break;
        }
    }

还有一种就是不使用Runtime.exec()方法,而是使用java自带的方法。

正则表达式的匹配

在正则表达式的构建过程中,如果使用用户自定义输入,同样的也需要进行输入校验。

考虑下面的正则表达式:

(.*? +public\[\d+\] +.*<SEARCHTEXT>.*)

上面的表达式本意是想在public[1234]这样的日志信息中,搜索用户的输入。

但是用户实际上可以输入下面的信息:

.*)|(.*

最终导致正则表达式变成下面的样子:

(.*? +public\[\d+\] +.*.*)|(.*.*)

从而导致匹配所有的日志信息。

解决方法也有两个,一个是使用白名单,判断用户的输入。一个是使用Pattern.quote()来对恶意字符进行转义。

本文的代码:

learn-java-base-9-to-20/tree/master/security

本文已收录于 http://www.flydean.com/java-security-code-line-input/

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

查看原文

flydean 发布了文章 · 9月21日

java安全编码指南之:输入校验

简介

为了保证java程序的安全,任何外部用户的输入我们都认为是可能有恶意攻击意图,我们需要对所有的用户输入都进行一定程度的校验。

本文将带领大家探讨一下用户输入校验的一些场景。一起来看看吧。

在字符串标准化之后进行校验

通常我们在进行字符串校验的时候需要对一些特殊字符进行过滤,过滤之后再进行字符串的校验。

我们知道在java中字符是基于Unicode进行编码的。但是在Unicode中,同一个字符可能有不同的表示形式。所以我们需要对字符进行标准化。

java中有一个专门的类Normalizer来负责处理,字符标准化的问题。

我们看下面一个例子:

    public void testNormalizer(){
        System.out.println(Normalizer.normalize("\u00C1", Normalizer.Form.NFKC));
        System.out.println(Normalizer.normalize("\u0041\u0301", Normalizer.Form.NFKC));
    }

输出结果:

Á
Á

我们可以看到,虽然两者的Unicode不一样,但是最终表示的字符是一样的。所以我们在进行字符验证的时候,一定要先进行normalize处理。

考虑下面的例子:

    public void falseNormalize(){
        String s = "\uFE64" + "script" + "\uFE65";
        Pattern pattern = Pattern.compile("[<>]"); // 检查是否有尖括号
        Matcher matcher = pattern.matcher(s);
        if (matcher.find()) {
            throw new IllegalStateException();
        }
        s = Normalizer.normalize(s, Normalizer.Form.NFKC);
    }

其中uFE64表示的是<,而uFE65表示的是>,程序的本意是判断输入的字符串是否包含了尖括号,但是因为直接传入的是unicode字符,所以直接compile是检测不到的。

我们需要对代码进行下面的改动:

    public void trueNormalize(){
        String s = "\uFE64" + "script" + "\uFE65";
        s = Normalizer.normalize(s, Normalizer.Form.NFKC);
        Pattern pattern = Pattern.compile("[<>]"); // 检查是否有尖括号
        Matcher matcher = pattern.matcher(s);
        if (matcher.find()) {
            throw new IllegalStateException();
        }
    }

先进行normalize操作,然后再进行字符验证。

注意不可信字符串的格式化

我们经常会使用到格式化来对字符串进行格式化,在格式化的时候如果格式化字符串里面带有用户输入信息,那么我们就要注意了。

看下面的例子:

    public void wrongFormat(){
        Calendar c = new GregorianCalendar(2020, GregorianCalendar.JULY, 27);
        String input=" %1$tm";
        System.out.format(input + " 时间不匹配,应该是某个月的第 %1$terd 天", c);
    }

粗看一下没什么问题,但是我们的input中包含了格式化信息,最后输出结果:

 07 时间不匹配,应该是某个月的第 27rd 天

变相的,我们获取到了系统内部的信息,在某些情况下面,可能会暴露系统的内部逻辑。

上面的例子我们应该将input也作为一个参数,如下所示:

    public void rightFormat(){
        Calendar c = new GregorianCalendar(2020, GregorianCalendar.JULY, 27);
        String input=" %1$tm";
        System.out.format("%s 时间不匹配,应该是某个月的第 %terd 天",input, c);
    }

输出结果:

 %1$tm 时间不匹配,应该是某个月的第 27rd 天

小心使用Runtime.exec()

我们知道Runtime.exec()使用来调用系统命令的,如果有恶意的用户调用了“rm -rf /”,一切的一切都完蛋了。

所以,我们在调用Runtime.exec()的时候,一定要小心注意检测用户的输入。

看下面的一个例子:

    public void wrongExec() throws IOException {
        String dir = System.getProperty("dir");
        Runtime rt = Runtime.getRuntime();
        Process proc = rt.exec(new String[] {"sh", "-c", "ls " + dir});
    }

上面的例子中,我们从系统属性中读取dir,然后执行了系统的ls命令来查看dir中的内容。

如果有恶意用户给dir赋值成:

/usr & rm -rf /

那么系统实际上执行的命令就是:

sh -c 'ls /usr & rm -rf /'

从而导致恶意的删除。

解决上面的问题也有几个方法,第一个方法就是对输入做个校验,比如我们只运行dir包含特定的字符:

    public void correctExec1() throws IOException {
        String dir = System.getProperty("dir");
        if (!Pattern.matches("[0-9A-Za-z@.]+", dir)) {
            // Handle error
        }
        Runtime rt = Runtime.getRuntime();
        Process proc = rt.exec(new String[] {"sh", "-c", "ls " + dir});
    }

第二种方法就是使用switch语句,限定特定的输入:

    public void correctExec2(){
        String dir = System.getProperty("dir");
        switch (dir){
            case "/usr":
                System.out.println("/usr");
                break;
            case "/local":
                System.out.println("/local");
                break;
            default:
                break;
        }
    }

还有一种就是不使用Runtime.exec()方法,而是使用java自带的方法。

正则表达式的匹配

在正则表达式的构建过程中,如果使用用户自定义输入,同样的也需要进行输入校验。

考虑下面的正则表达式:

(.*? +public\[\d+\] +.*<SEARCHTEXT>.*)

上面的表达式本意是想在public[1234]这样的日志信息中,搜索用户的输入。

但是用户实际上可以输入下面的信息:

.*)|(.*

最终导致正则表达式变成下面的样子:

(.*? +public\[\d+\] +.*.*)|(.*.*)

从而导致匹配所有的日志信息。

解决方法也有两个,一个是使用白名单,判断用户的输入。一个是使用Pattern.quote()来对恶意字符进行转义。

本文的代码:

learn-java-base-9-to-20/tree/master/security

本文已收录于 http://www.flydean.com/java-security-code-line-input/

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

查看原文

赞 1 收藏 1 评论 0

flydean 收藏了文章 · 9月18日

java安全编码指南之:堆污染Heap pollution

简介

什么是堆污染呢?堆污染是指当参数化类型变量引用的对象不是该参数化类型的对象时而发生的。

我们知道在JDK5中,引入了泛型的概念,我们可以在创建集合类的时候,指定该集合类中应该存储的对象类型。

如果在指定类型的集合中,引用了不同的类型,那么这种情况就叫做堆污染。

产生堆污染的例子

有同学可能会问了,既然JDK5引入了泛型,为什么还会出现堆污染呢?

这是一个好问题,让我们看一个例子:

    public void heapPollution1(){
        List normalList= Arrays.asList("www.flydean.com",100);
        List<Integer> integerList= normalList;
    }

上面的例子中,我们使用Arrays.asList创建了一个普通的List。

这个List中包含了int和String两种类型,当我们将List赋值给List<Integer>的时候,java编译器并不会去判断赋值List中的类型,integerList中包含了非Integer的元素,最终导致在使用的时候会出现错误。

直接给List<Integer>赋值不会进行类型检查,那么如果我们是直接向List<Integer>中添加元素呢?

我们看下下面的例子:

    private void addToList(List list, Object object){
        list.add(object);
    }

    @Test
    public void heapPollution2(){
        List<Integer> integerList=new ArrayList<>();
        addToList(integerList,"www.flydean.com");
    }

上面的例子中,我们定义了一个addToList方法,这个方法的参数是一个普通的List,但是我们传入了一个List<Integer>。

结果,我们发现list.add方法并没有进行参数类型校验。

上面的例子该怎么修改呢?

我们需要在addToList方法的List参数中,也添加上类型校验:

    private void addToList(List<Integer> list, Object object){
        list.add(object);
    }

如果addToList是一个非常通用的方法怎么办呢?在addToList的参数中添加参数类型是现实的。

这个时候,我们可以考虑使用Collections.checkedList方法来将输入的List转换成为一个checkedList,从而只接收特定类型的元素。

    public void heapPollutionRight(){
        List<Integer> integerList=new ArrayList<>();
        List<Integer> checkedIntegerList= Collections.checkedList(integerList, Integer.class);
        addToList(checkedIntegerList,"www.flydean.com");
    }

运行上面的代码,我们将会得到下面的异常:

java.lang.ClassCastException: Attempt to insert class java.lang.String element into collection with element type class java.lang.Integer

更通用的例子

上面我们定义了一个addToList方法,因为没有做类型判断,所以可能会出现堆污染的问题。

有没有什么办法既可以通用,又可以避免堆污染呢?

当然有的,我们看下面的实现:

    private <T> void addToList2(List<T> list, T t) {
        list.add(t);
    }

    public <T> void heapPollutionRight2(T element){
        List<T> list = new ArrayList<>();
        addToList2(list,element);
    }

上面的例子中,我们在addToList方法中定义了一个参数类型T,通过这样,我们保证了List中的元素类型的一致性。

可变参数

事实上,方法参数可以是可变的,我们考虑下面的例子:

    private void addToList3(List<Integer>... listArray){
        Object[] objectArray = listArray;
        objectArray[0]= Arrays.asList("www.flydean.com");
        for(List<Integer> integerList: listArray){
            for(Integer element: integerList){
                System.out.println(element);
            }
        }
    }

上面的例子中我们的参数是一个List的数组,虽然List中的元素类型固定了,但是我们可以重新赋值给参数数组,从而实际上修改掉参数类型。

如果上面addToList3的方法参数修改为下面的方式,就不会出现问题了:

private void addToList4(List<List<Integer>> listArray){

这种情况下,List的类型是固定的,我们无法通过重新赋值的方式来修改它。

本文的例子:

learn-java-base-9-to-20/tree/master/security

本文已收录于 http://www.flydean.com/java-security-code-line-heap-pollution/

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

查看原文

flydean 发布了文章 · 9月18日

java安全编码指南之:堆污染Heap pollution

简介

什么是堆污染呢?堆污染是指当参数化类型变量引用的对象不是该参数化类型的对象时而发生的。

我们知道在JDK5中,引入了泛型的概念,我们可以在创建集合类的时候,指定该集合类中应该存储的对象类型。

如果在指定类型的集合中,引用了不同的类型,那么这种情况就叫做堆污染。

产生堆污染的例子

有同学可能会问了,既然JDK5引入了泛型,为什么还会出现堆污染呢?

这是一个好问题,让我们看一个例子:

    public void heapPollution1(){
        List normalList= Arrays.asList("www.flydean.com",100);
        List<Integer> integerList= normalList;
    }

上面的例子中,我们使用Arrays.asList创建了一个普通的List。

这个List中包含了int和String两种类型,当我们将List赋值给List<Integer>的时候,java编译器并不会去判断赋值List中的类型,integerList中包含了非Integer的元素,最终导致在使用的时候会出现错误。

直接给List<Integer>赋值不会进行类型检查,那么如果我们是直接向List<Integer>中添加元素呢?

我们看下下面的例子:

    private void addToList(List list, Object object){
        list.add(object);
    }

    @Test
    public void heapPollution2(){
        List<Integer> integerList=new ArrayList<>();
        addToList(integerList,"www.flydean.com");
    }

上面的例子中,我们定义了一个addToList方法,这个方法的参数是一个普通的List,但是我们传入了一个List<Integer>。

结果,我们发现list.add方法并没有进行参数类型校验。

上面的例子该怎么修改呢?

我们需要在addToList方法的List参数中,也添加上类型校验:

    private void addToList(List<Integer> list, Object object){
        list.add(object);
    }

如果addToList是一个非常通用的方法怎么办呢?在addToList的参数中添加参数类型是现实的。

这个时候,我们可以考虑使用Collections.checkedList方法来将输入的List转换成为一个checkedList,从而只接收特定类型的元素。

    public void heapPollutionRight(){
        List<Integer> integerList=new ArrayList<>();
        List<Integer> checkedIntegerList= Collections.checkedList(integerList, Integer.class);
        addToList(checkedIntegerList,"www.flydean.com");
    }

运行上面的代码,我们将会得到下面的异常:

java.lang.ClassCastException: Attempt to insert class java.lang.String element into collection with element type class java.lang.Integer

更通用的例子

上面我们定义了一个addToList方法,因为没有做类型判断,所以可能会出现堆污染的问题。

有没有什么办法既可以通用,又可以避免堆污染呢?

当然有的,我们看下面的实现:

    private <T> void addToList2(List<T> list, T t) {
        list.add(t);
    }

    public <T> void heapPollutionRight2(T element){
        List<T> list = new ArrayList<>();
        addToList2(list,element);
    }

上面的例子中,我们在addToList方法中定义了一个参数类型T,通过这样,我们保证了List中的元素类型的一致性。

可变参数

事实上,方法参数可以是可变的,我们考虑下面的例子:

    private void addToList3(List<Integer>... listArray){
        Object[] objectArray = listArray;
        objectArray[0]= Arrays.asList("www.flydean.com");
        for(List<Integer> integerList: listArray){
            for(Integer element: integerList){
                System.out.println(element);
            }
        }
    }

上面的例子中我们的参数是一个List的数组,虽然List中的元素类型固定了,但是我们可以重新赋值给参数数组,从而实际上修改掉参数类型。

如果上面addToList3的方法参数修改为下面的方式,就不会出现问题了:

private void addToList4(List<List<Integer>> listArray){

这种情况下,List的类型是固定的,我们无法通过重新赋值的方式来修改它。

本文的例子:

learn-java-base-9-to-20/tree/master/security

本文已收录于 http://www.flydean.com/java-security-code-line-heap-pollution/

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

欢迎关注我的公众号:「程序那些事」,懂技术,更懂你!

查看原文

赞 1 收藏 1 评论 0

认证与成就

  • 获得 282 次点赞
  • 获得 5 枚徽章 获得 0 枚金徽章, 获得 2 枚银徽章, 获得 3 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

注册于 1月9日
个人主页被 1.1k 人浏览