fixer.go

Documentation: github.com/google/certificate-transparency-go/fixchain

     1  // Copyright 2016 Google LLC. All Rights Reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package fixchain
    16  
    17  import (
    18  	"bytes"
    19  	"log"
    20  	"net/http"
    21  	"sort"
    22  	"sync"
    23  	"sync/atomic"
    24  	"time"
    25  
    26  	"github.com/google/certificate-transparency-go/x509"
    27  )
    28  
    29  // Fixer contains methods to asynchronously fix certificate chains and
    30  // properties to store information about each attempt that is made to fix a
    31  // certificate chain.
    32  type Fixer struct {
    33  	toFix  chan *toFix
    34  	chains chan<- []*x509.Certificate // Chains successfully fixed by the fixer
    35  	errors chan<- *FixError
    36  
    37  	active uint32
    38  
    39  	reconstructed       uint32
    40  	notReconstructed    uint32
    41  	fixed               uint32
    42  	notFixed            uint32
    43  	validChainsProduced uint32
    44  	validChainsOut      uint32
    45  
    46  	wg    sync.WaitGroup
    47  	cache *urlCache
    48  }
    49  
    50  // QueueChain adds the given cert and chain to the queue to be fixed by the
    51  // fixer, with respect to the given roots.  Note: chain is expected to be in the
    52  // order of cert --> root.
    53  func (f *Fixer) QueueChain(cert *x509.Certificate, chain []*x509.Certificate, roots *x509.CertPool) {
    54  	f.toFix <- &toFix{
    55  		cert:  cert,
    56  		chain: newDedupedChain(chain),
    57  		roots: roots,
    58  		cache: f.cache,
    59  	}
    60  }
    61  
    62  // Wait for all the fixer workers to finish.
    63  func (f *Fixer) Wait() {
    64  	close(f.toFix)
    65  	f.wg.Wait()
    66  }
    67  
    68  func (f *Fixer) updateCounters(chains [][]*x509.Certificate, ferrs []*FixError) {
    69  	atomic.AddUint32(&f.validChainsProduced, uint32(len(chains)))
    70  
    71  	var verifyFailed bool
    72  	var fixFailed bool
    73  	for _, ferr := range ferrs {
    74  		switch ferr.Type {
    75  		case VerifyFailed:
    76  			verifyFailed = true
    77  		case FixFailed:
    78  			fixFailed = true
    79  		}
    80  	}
    81  	// No errors --> reconstructed
    82  	// VerifyFailed --> notReconstructed
    83  	// VerifyFailed but no FixFailed --> fixed
    84  	// VerifyFailed and FixFailed --> notFixed
    85  	if verifyFailed {
    86  		atomic.AddUint32(&f.notReconstructed, 1)
    87  		// FixFailed error will only be present if a VerifyFailed error is, as
    88  		// fixChain() is only called if constructChain() fails.
    89  		if fixFailed {
    90  			atomic.AddUint32(&f.notFixed, 1)
    91  			return
    92  		}
    93  		atomic.AddUint32(&f.fixed, 1)
    94  		return
    95  	}
    96  	atomic.AddUint32(&f.reconstructed, 1)
    97  }
    98  
    99  // chainSlice contains chains of certificates. Applying Sort will sort in
   100  // order of the first certificate in the chain, i.e. their leaf certificate.
   101  // If two chains have equal leaf certificates, they will be sorted by the
   102  // second certificate in the chain, and so on.  By this logic, a chain that
   103  // is a subchain of another chain beginning at the leaf of the other chain,
   104  // will come before the other chain after sorting.
   105  //
   106  // Example:
   107  //
   108  // Before sorting:
   109  // A -> B -> C
   110  // D
   111  // A -> C
   112  // A -> B
   113  //
   114  // After sorting:
   115  // A -> B
   116  // A -> B -> C
   117  // A -> C
   118  // D
   119  type chainSlice struct {
   120  	chains [][]*x509.Certificate
   121  }
   122  
   123  func min(a, b int) int {
   124  	if a < b {
   125  		return a
   126  	}
   127  	return b
   128  }
   129  
   130  // Len implements sort.Sort(data Interface) for chainSlice.
   131  func (c chainSlice) Len() int { return len(c.chains) }
   132  
   133  // Less implements sort.Sort interface for chainSlice.
   134  func (c chainSlice) Less(i, j int) bool {
   135  	chi := c.chains[i]
   136  	chj := c.chains[j]
   137  	for k := 0; k < min(len(chi), len(chj)); k++ {
   138  		if !chi[k].Equal(chj[k]) {
   139  			return bytes.Compare(chi[k].Raw, chj[k].Raw) < 0
   140  		}
   141  	}
   142  	return len(chi) < len(chj)
   143  }
   144  
   145  // Swap implements sort.Sort interface for chainSlice.
   146  func (c chainSlice) Swap(i, j int) {
   147  	t := c.chains[i]
   148  	c.chains[i] = c.chains[j]
   149  	c.chains[j] = t
   150  }
   151  
   152  // removeSuperChains will remove super chains from the list of chains passed to
   153  // it.  A super chain is considered to be a chain whose first x certificates are
   154  // included in the list somewhere else as a whole chain.  Put another way, if
   155  // there exists a chain A in the list, and another chain B that is A with some
   156  // additional certificates chained onto the end, B is a super chain of A
   157  // (and A is a subchain of B).
   158  //
   159  // Examples:
   160  //  1. A -> B -> C is a super chain of A -> B, and both are super chains of A.
   161  //  2. Z -> A -> B is not a super chain of A -> B, as A -> B is not at the
   162  //     beginning of Z -> A -> B.
   163  //  3. Calling removeSuperChains on:
   164  //     A -> B -> C
   165  //     A -> C
   166  //     A -> B
   167  //     A -> C -> D
   168  //     will return:
   169  //     A -> B
   170  //     A -> C
   171  //  4. Calling removeSuperChains on:
   172  //     A -> B -> C
   173  //     A -> C
   174  //     A -> B
   175  //     A -> C -> D
   176  //     A
   177  //     will return:
   178  //     A
   179  func removeSuperChains(chains [][]*x509.Certificate) [][]*x509.Certificate {
   180  	// Sort the list of chains using the sorting algorithm described above.
   181  	// This will result in chains and their super chains being grouped together
   182  	// in the list, with the shortest chain listed first in the group (i.e. a
   183  	// chain, and then all its super chains - if any - listed directly after
   184  	// that chain).
   185  	c := chainSlice{chains: chains}
   186  	sort.Sort(c)
   187  	var retChains [][]*x509.Certificate
   188  NextChain:
   189  	// Start at the beginning of the list.
   190  	for i := 0; i < len(c.chains); {
   191  		// Add the chain to the list of chains to be returned.
   192  		retChains = append(retChains, c.chains[i])
   193  		// Step past any super chains of the chain just added to the return list,
   194  		// without adding them to the return list.  We do not want super chains
   195  		// of other chains in our return list.  Due to the initial sort of the
   196  		// list, any super chains of a chain will come directly after said chain.
   197  		for j := i + 1; j < len(c.chains); j++ {
   198  			for k := range c.chains[i] {
   199  				// When a chain that is not a super chain of the chain most
   200  				// recently added to the return list is found, move to that
   201  				// chain and start over.
   202  				if !c.chains[i][k].Equal(c.chains[j][k]) {
   203  					i = j
   204  					continue NextChain
   205  				}
   206  			}
   207  		}
   208  		break
   209  	}
   210  	return retChains
   211  }
   212  
   213  func (f *Fixer) fixServer() {
   214  	defer f.wg.Done()
   215  
   216  	for fix := range f.toFix {
   217  		atomic.AddUint32(&f.active, 1)
   218  		chains, ferrs := fix.handleChain()
   219  		f.updateCounters(chains, ferrs)
   220  		for _, ferr := range ferrs {
   221  			f.errors <- ferr
   222  		}
   223  
   224  		// If handleChain() outputs valid chains that are subchains of other
   225  		// valid chains, (where the subchains start at the leaf)
   226  		// e.g. A -> B -> C and A -> B -> C -> D, only forward on the shorter
   227  		// of the chains.
   228  		for _, chain := range removeSuperChains(chains) {
   229  			f.chains <- chain
   230  			atomic.AddUint32(&f.validChainsOut, 1)
   231  		}
   232  		atomic.AddUint32(&f.active, ^uint32(0))
   233  	}
   234  }
   235  
   236  func (f *Fixer) newFixServerPool(workerCount int) {
   237  	for i := 0; i < workerCount; i++ {
   238  		f.wg.Add(1)
   239  		go f.fixServer()
   240  	}
   241  }
   242  
   243  func (f *Fixer) logStats() {
   244  	t := time.NewTicker(time.Second)
   245  	go func() {
   246  		for range t.C {
   247  			log.Printf("fixers: %d active, %d reconstructed, "+
   248  				"%d not reconstructed, %d fixed, %d not fixed, "+
   249  				"%d valid chains produced, %d valid chains sent",
   250  				f.active, f.reconstructed, f.notReconstructed,
   251  				f.fixed, f.notFixed, f.validChainsProduced, f.validChainsOut)
   252  		}
   253  	}()
   254  }
   255  
   256  // NewFixer creates a new asynchronous fixer and starts up a pool of
   257  // workerCount workers.  Errors are pushed to the errors channel, and fixed
   258  // chains are pushed to the chains channel.  client is used to try to get any
   259  // missing certificates that are needed when attempting to fix chains.
   260  func NewFixer(workerCount int, chains chan<- []*x509.Certificate, errors chan<- *FixError, client *http.Client, logStats bool) *Fixer {
   261  	f := &Fixer{
   262  		toFix:  make(chan *toFix),
   263  		chains: chains,
   264  		errors: errors,
   265  		cache:  newURLCache(client, logStats),
   266  	}
   267  
   268  	f.newFixServerPool(workerCount)
   269  	if logStats {
   270  		f.logStats()
   271  	}
   272  	return f
   273  }
   274
View as plain text