USB tethering gone after upgrading to iOS 9 and iTunes 12.3
Update:
Per @SeeMeCode's answer, you can re-install iTunes to solve the problem.

Solved.
I found the solution here. It's caused by a damaged kernel extension /System/Library/Extensions/AppleUSBEthernetHost.kext.
When I check /var/log/system.log, sure enough there is:
Sep 17 08:00:58 wagner.local com.apple.kextd[45]: Kext id com.apple.driver.AppleUSBHostMergeProperties not found; removing personalities from kernel.
Sep 17 08:00:58 wagner.local com.apple.kextd[45]: ERROR: invalid signature for com.apple.macos.driver.AppleUSBEthernetHost, will not load

This extension is installed with iTunes, so the cause was update to iTunes 12.3, not iOS 9. I tried to download iTunes and reinstall it, but it just installed the same damaged version of the kernel extension. So instead, I replaced it from a Time Machine backup as both the currently installed and the backed up version had the same version number 7.0.
After a restart, USB tethering works again.
To distinguish between the two, here's what the working one looks like:

$ ls -lR /System/Library/Extensions/AppleUSBEthernetHost.kext
total 0
drwxr-xr-x  6 root  wheel  204 Jan 10  2015 Contents

/System/Library/Extensions/AppleUSBEthernetHost.kext/Contents:
total 16
-rw-r--r--  1 root  wheel  3202 Jan 10  2015 Info.plist
drwxr-xr-x  3 root  wheel   102 Jan 10  2015 MacOS
drwxr-xr-x  3 root  wheel   102 Jan 10  2015 _CodeSignature
-rw-r--r--  1 root  wheel   474 Jan 10  2015 version.plist

/System/Library/Extensions/AppleUSBEthernetHost.kext/Contents/MacOS:
total 128
-rwxr-xr-x  1 root  wheel  63024 Jan 10  2015 AppleUSBEthernetHost

/System/Library/Extensions/AppleUSBEthernetHost.kext/Contents/_CodeSignature:
total 8
-rw-r--r--  1 root  wheel  3668 Jan 10  2015 CodeResources

And the damaged one:

$ ls -lR AppleUSBEthernetHost.kext
total 0
drwxr-xr-x  5 ischeini  staff  170 Aug  5 00:30 Contents

Contents:
total 16
-rw-r--r--@ 1 ischeini  staff  3202 Aug  5 00:30 Info.plist
drwxr-xr-x  3 ischeini  staff   102 Aug  5 00:30 MacOS
-rw-r--r--@ 1 ischeini  staff   473 Aug  5 00:30 version.plist

Contents/MacOS:
total 144
-rwxr-xr-x@ 1 ischeini  staff  71792 Aug  5 00:30 AppleUSBEthernetHost