That paper is from 2014 and some of the circumstances described have since changed.
They've also done some things that I assume fell out of operating ICSI's Notary but don't make any real sense for this paper.
For example: For a real user what we care about is this cert the end user was presented for a site: Would that be trusted in (Internet Explorer on XP, Safari on iOS, a Python script on a Debian machine, etcetera) and would it be trusted in this smartphone.
And what they've looked at is, were the same Trust Stores baked into an Android phone as the above systems? But that's subtly different in a way that fogs the issue here. Example:
Suppose phone X trusts ISRG Root X1, XP trusts DST Root CA X 3, and a Debian system trusts Lets Encrypt Authority X3. Those are, to the naked eye, and this study, three completely different things. But in _practice_ for an end user it'd turn out any of the three work for trusting a vast number of certificates used on the web. Trusting one or another _does_ matter, but this paper isn't about why that is, and doesn't really explain what's going on here, it treats that sort of scenario as anomalous and potentially alarming without explaining.
The paper did remind me that ICSI's Notary won't work with TLS 1.3, which I have sort of known but not ever mentally addressed. The ICSI Notary works by peeking inside TLS sessions. In versions up to TLS 1.2, the server's Certificate is delivered unencrypted, just before both peers encryption switches on and their communications are unintelligible. This is used by the Notary and by lots of crappy middleboxes, but in TLS 1.3 the encryption has switched on earlier, before the certificate is sent, so the Notary can't see certificates any more.